{"id":1497,"date":"2019-04-11T03:30:50","date_gmt":"2019-04-11T03:30:50","guid":{"rendered":"http:\/\/www.afternerd.com\/blog\/?p=1497"},"modified":"2019-08-23T04:05:25","modified_gmt":"2019-08-23T04:05:25","slug":"flatten-binary-tree-linked-list","status":"publish","type":"post","link":"https:\/\/www.afternerd.com\/blog\/flatten-binary-tree-linked-list\/","title":{"rendered":"Python: Flatten Binary Tree to Linked List"},"content":{"rendered":"

In this article, I will solve a common Tree<\/a> data-structure question. This question also appears frequently in coding interviews<\/a>.<\/p>\n

In solving this question, I will also teach you the thought process that I go through when I encounter problems like this one so you can solve similar problems on your own if you encounter them.<\/p>\n

I am also going to provide you with an in-depth explanation of the code, how it works, and what its time complexity is.<\/p>\n

The Question<\/h2>\n

The question goes as follows:<\/em><\/p>\n

Given a binary tree, flatten the tree into a linked list in place.<\/p>\n

For example, if this is the input tree<\/p>\n

\"\"<\/p>\n

The output linked list should look like this<\/p>\n

\"\"<\/p>\n

And since we are making this conversion in place, you can assume that the Tree’s right<\/strong> pointer is equivalent to a Linked List’s next<\/strong> pointer.<\/p>\n

The Thought Process<\/h2>\n

As with all tree data structure questions, the first thing that comes to my mind when I am faced with a tree data-structure problem is to think if there is a way to solve the problem recursively through a divide and conquer<\/strong> algorithm.<\/p>\n

In other words,\u00a0 can I construct a solution to the main problem given the solutions of subproblems?<\/p>\n

Pro tip:<\/strong> In most tree data-structure questions, this is actually true.<\/div>\n

Alright, let’s go back to our problem and try to examine it again from this angle.<\/p>\n

By looking at the example shown, it is very obvious that the head of the output linked list is the root<\/strong> of the tree node, followed by a flattened left subtree<\/strong>, which is followed by a flattened right subtree<\/strong>.<\/p>\n

This simple description above is our solution.<\/p>\n

How you ask?<\/p>\n

Well, flattening the left subtree and the right subtree are the sub-problems that I talked about earlier which we can just delegate to the magic of recursion.<\/p>\n

Now the question is, given the solutions of these subproblems, how can we construct a solution to the main tree.<\/p>\n

Let’s first see how the tree will look like after we flatten the left and right subtrees.<\/p>\n

If we recursively flatten the left subtree and the right subtree, we will not precisely end up with the output linked list that we are looking for.<\/p>\n

Instead, we will end up with a tree that looks like this.<\/p>\n

\"\"<\/p>\n

This means we still need to do some more work to construct the final output, but we are in a much better state now.<\/p>\n

So how can we do that?<\/em><\/p>\n

It’s actually very simple.<\/p>\n

Step 1:<\/strong> The right pointer of root should point to the head of the flattened left subtree<\/p>\n

Step 2:<\/strong> The right pointer of the tail of the left subtree should point to the head of the right subtree<\/p>\n

Step 3:<\/strong> The left pointer of root should point to None<\/strong><\/p>\n

The Code<\/h2>\n

Now after this thought process that we went through, translating the solution that we came up with into code is very straight-forward.<\/p>\n

That’s why I encourage you, whether you are in a coding interview or not, to spend some time thinking about your solution and improving it before you dive into writing code.<\/p>\n

Because most of the time, writing the code is the easiest part.<\/p>\n

Now let’s start coding our solution up<\/p>\n

def flatten(root):\r\n   if root is not None:\r\n     flatten(root.left)\r\n     flatten(root.right)\r\n     if root.left is not None:\r\n       current = root.left\r\n       while current.right is not None:\r\n         current = current.right\r\n\r\n       current.right = root.right\r\n       root.right = root.left\r\n       root.left = None<\/code><\/pre>\n
Explaining the Code<\/h2>\n
Since this is a recursive solution, you have to think of the base case(s).<\/p>\n
Otherwise your code will run infinitely and neither your processor or your memory will be happy :).<\/p>\n
Personally, when I am solving a problem in a recursive manner, I tend to think about the recursive part of the solution first before I start thinking about the base cases.<\/p>\n
But it’s up to you to figure out which way you’re more comfortable with.<\/p>\n
So what do you think the base case is for this problem?<\/h3>\n
To answer this, let’s first remember that our function doesn’t actually return anything. Everything happens in place.<\/p>\n
Since we are recursively flattening the left and right subtrees for each node, the questions is when do we stop?<\/p>\n
We can stop when we encounter a None tree node.<\/strong><\/p>\n
When we encounter a None tree node<\/strong>, we call it a day and we stop recursing any further.<\/p>\n
So the base case is:<\/p>\n
if root is None: return<\/code><\/pre>\n
But instead of saying that, we can also also embed all your logic in the opposite if statement<\/p>\n
if root is not None: # your logic here<\/code><\/pre>\n
And this is what we have in line number 2<\/strong><\/p>\n
Line number 3<\/strong> and line number 4<\/strong> are the magical recursive function calls that solve the subproblems for the left and right subtrees.<\/p>\n
flatten(root.left)\r\nflatten(root.right)<\/code><\/pre>\n
Starting from line number 5<\/strong>, what we are essentially doing is constructing the solution of the main problem from the solutions of subproblems.<\/p>\n
But first I want you notice something.<\/p>\n
What do you think should happen if our tree doesn’t have a left subtree?<\/strong><\/p>\n
Think about it.<\/p>\n
As a matter of fact, if there is no left subtree then we don’t need to do any extra work since the right subtree is already flattened, the root’s left pointer is pointing to None, and the root’s right pointer is pointing to the head of the right subtree.<\/p>\n
Sweet! we are done.<\/p>\n
It’s only if the left subtree exists that we need to do some extra work.<\/p>\n
Specifically, we need to do 3 things:<\/p>\n
1. Find the tail of the flattened left subtree<\/h3>\n
Since the left subtree is already flattened, you can use a simple loop to reach the tail<\/p>\n
current = root.left\r\nwhile current.right is not None:\r\n  current = current.right<\/code><\/pre>\n
After the loop terminates, current<\/strong> will be pointing to the tail of the left subtree.<\/p>\n
2. Connect the tail of the left subtree with the head of the flattened right subtree<\/h3>\n
Now that we identified the tail of the left subtree, we need to modify the tail’s right(next) pointer to point to the head of the flattened right subtree.<\/p>\n
This is what this pice of code does.<\/p>\n
current.right = root.right<\/code><\/pre>\n
\u00a03. Modify the root’s left and right pointers<\/h3>\n
Finally, we need to modify the root’s right pointer to point to the flattened left subtree and left one to point to None<\/strong>.<\/p>\n
root.right = root.left\r\nroot.left = None<\/code><\/pre>\n
Time Complexity<\/h2>\n
We can use Master theorem<\/a> to find out the time complexity for our algorithm.<\/p>\n
If you are not familiar with Master theorem, I highly recommend that you take a look and familiarize yourself with it.<\/p>\n
Sometimes, using Master theorem is the simplest way to analyze the time complexity of a recursive algorithm.<\/p>\n
Now let’s see how we can analyze our recursive algorithm.<\/p>\n
Basically, to solve this problem for a tree of size n, we need to solve two subproblems for the left and right subtrees.<\/p>\n
In the average case, let’s assume that each subtree will be of size (n\/2).<\/p>\n
After the two subproblems have been resolved, constructing the solution of the original problem requires finding the tail of the left subtree which is O(log n).<\/p>\n
With this information, we can write the recursive formula as:<\/p>\n
T(n) = 2 * T(n \/ 2) + o(log n)<\/span><\/p>\n
By applying the Master theorem to this formula<\/a>, we get that the run time is O(n).<\/p>\n
\n
Struggling with Tree data structure questions?<\/h2>\n
Master Tree coding interview questions with my e-book<\/h3>\n
Here is what you will get in the e-book:<\/p>\n
    \n
  • 14 problems that cover the majority of ideas for Tree coding interview questions<\/li>\n
  • In-depth explanation to each solution (like this article)<\/li>\n
  • The thought process that will help you arrive at the right solution<\/li>\n
  • How to approach solving any tree coding interview question even if you haven’t seen the question before<\/li>\n<\/ul>\n
    Get the E-book now for only $4.99!<\/h3>\n