Python tree to list

Python: Flatten Binary Tree to Linked List

In this article, I will solve a common Tree data-structure question. This question also appears frequently in coding interviews.

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.

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

The Question

The question goes as follows:

Given a binary tree, flatten the tree into a linked list in place.

For example, if this is the input tree

The output linked list should look like this

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

The Thought Process

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 algorithm.

In other words, can I construct a solution to the main problem given the solutions of subproblems?

Alright, let’s go back to our problem and try to examine it again from this angle.

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

This simple description above is our solution.

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.

Now the question is, given the solutions of these subproblems, how can we construct a solution to the main tree.

Let’s first see how the tree will look like after we flatten the left and right subtrees.

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.

Instead, we will end up with a tree that looks like this.

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

Step 1: The right pointer of root should point to the head of the flattened left subtree

Step 2: The right pointer of the tail of the left subtree should point to the head of the right subtree

Step 3: The left pointer of root should point to None

The Code

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

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.

Because most of the time, writing the code is the easiest part.

Now let’s start coding our solution up

def flatten(root): if root is not None: flatten(root.left) flatten(root.right) if root.left is not None: current = root.left while current.right is not None: current = current.right current.right = root.right root.right = root.left root.left = None

Explaining the Code

Since this is a recursive solution, you have to think of the base case(s).

Otherwise your code will run infinitely and neither your processor or your memory will be happy :).

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.

But it’s up to you to figure out which way you’re more comfortable with.

So what do you think the base case is for this problem?

To answer this, let’s first remember that our function doesn’t actually return anything. Everything happens in place.

Since we are recursively flattening the left and right subtrees for each node, the questions is when do we stop?

We can stop when we encounter a None tree node.

When we encounter a None tree node, we call it a day and we stop recursing any further.

But instead of saying that, we can also also embed all your logic in the opposite if statement

if root is not None: # your logic here

And this is what we have in line number 2

Line number 3 and line number 4 are the magical recursive function calls that solve the subproblems for the left and right subtrees.

flatten(root.left) flatten(root.right)

Starting from line number 5, what we are essentially doing is constructing the solution of the main problem from the solutions of subproblems.

But first I want you notice something.

What do you think should happen if our tree doesn’t have a left subtree?

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.

It’s only if the left subtree exists that we need to do some extra work.

Specifically, we need to do 3 things:

1. Find the tail of the flattened left subtree

Since the left subtree is already flattened, you can use a simple loop to reach the tail

current = root.left while current.right is not None: current = current.right

After the loop terminates, current will be pointing to the tail of the left subtree.

2. Connect the tail of the left subtree with the head of the flattened right subtree

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.

This is what this pice of code does.

3. Modify the root’s left and right pointers

Finally, we need to modify the root’s right pointer to point to the flattened left subtree and left one to point to None.

root.right = root.left root.left = None

Time Complexity

We can use Master theorem to find out the time complexity for our algorithm.

If you are not familiar with Master theorem, I highly recommend that you take a look and familiarize yourself with it.

Sometimes, using Master theorem is the simplest way to analyze the time complexity of a recursive algorithm.

Now let’s see how we can analyze our recursive algorithm.

Basically, to solve this problem for a tree of size n, we need to solve two subproblems for the left and right subtrees.

In the average case, let’s assume that each subtree will be of size (n/2).

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).

With this information, we can write the recursive formula as:

Struggling with Tree data structure questions?

Master Tree coding interview questions with my e-book

Here is what you will get in the e-book:

• 14 problems that cover the majority of ideas for Tree coding interview questions
• In-depth explanation to each solution (like this article)
• The thought process that will help you arrive at the right solution
• How to approach solving any tree coding interview question even if you haven’t seen the question before

Источник

Returning a list of the values from the binary tree

I want to return a list of the values from the binary tree. Is there a shorter and more efficient way to write the method for numbers?

class BTNode(object): """A node in a binary tree.""" def __init__(self, item, left=None, right=None): """(BTNode, object, BTNode, BTNode) -> NoneType Initialize this node to store item and have children left and right, as well as depth 0. """ self.item = item self.left = left self.right = right self.depth = 0 # the depth of this node in a tree def number(self: 'BTNode') -> list: lst = [] if self.right is None and self.left is None: lst.append(self.item) else: lst.append(self.item) if self.left: left = self.left.number() lst.extend(left) if self.right: right = self.right.number() lst.extend(right) return lst 

2 Answers 2

1. There is no docstring for the number method.
2. There are no test cases. This kind of code would be an ideal opportunity to write some doctests.
3. The depth property is always 0. This seems useless.
4. The method name number is misleading. (It does not return a number.) I would call it something like flattened_pre_order because it flattens the tree into a list using pre-order traversal.
5. The variable name lst is misspelt. Better to call it something like result .
6. This code:

if self.right is None and self.left is None: lst.append(self.item) else: lst.append(self.item) 

>>> n = None >>> for i in range(1000): n = BTNode(i, n) . >>> n.number() Traceback (most recent call last): File "", line 1, in File "cr33662.py", line 22, in number left = self.left.number() [. many lines omitted . ] RuntimeError: maximum recursion depth exceeded 

def flattened_pre_order(self: 'BTNode') -> list: """Return a list of items in the tree rooted at this node, using pre-order traversal. >>> tree = BTNode(1, BTNode(2, None, BTNode(3)), BTNode(4)) >>> tree.flattened_pre_order() [1, 2, 3, 4] >>> node = BTNode(9999) >>> for i in range(9998, -1, -1): node = BTNode(i, node) >>> node.flattened_pre_order() == list(range(10000)) True """ result = [] stack = [self] node = None while stack: if node is None: node = stack.pop() if node is not None: result.append(node.item) stack.append(node.right) node = node.left return result 

Источник

Iterative tree traversal to turn tree into a dictionary and list

\$\begingroup\$ I’m probably telling you nothing new @Kevin, but — as a general rule you may want to profile your module, and see where it spends most of its time, and where the most memory is being used. Then, concentrate your efforts at the heavy-hitters. huyng.com/posts/python-performance-analysis and stackoverflow.com/questions/582336/… may help. \$\endgroup\$

1 Answer 1

Empty lists are False , so while len(stack) != 0 is the same as while stack . None is also False , so you can check for empty lists and None values at the same time.

You can use dict.setdefault to get a value and set it to a default (in your case an empty list). if it isn’t already there.

You can convert an append loop to extend with a generator expression, or better yet just a zip .

Your last two elif tests are mutually exclusive, so the last can be an else .

The if node_tuple[1] == layer: test does the same thing in the first line of both cases. I moved that out of the if test, but if they are supposed to do something different you should fix that yourself.

pre_layer always has its value subtracted by one, so it is easier to subtract one before defining it.

You always set node_tuple to stack[-1] if stack is non-empty, so you can move that out of the if test entirely. And if you put it at the beginning of the loop, you can avoid the if test entirely. You can simplify this further by only getting it if you need it.

def reconstruct_iteratively(root): # A tuple that stores node to be traverse and the layer the node is in stack = [(root, 0)] layer = 0 pre_layer = -1 level = dict() # This is a postorder traversal while stack: node_value, node_layer = stack[-1] node_list = node_value.node_list # This case catch the event that next node is the parent layer and # this node is not a termination node if node_layer < pre_layer: parent_node = stack.pop() parent_node_dict = layer -= 1 pre_layer = layer level.setdefault(layer, []).append(parent_node_dict) # This case catch the event for traversing down to the child elif node_list: stack.extend(zip(node_list, [layer+1]*len(node_list))) layer += 1 # This case catch the event that we are at the termination node else: # Two possible scenario # 1. The next node is in the same layer # 2. The next node is in the parent layer level.setdefault(layer, []).append() del stack[-1] if stack[-1][1] != layer: parent_node_dict = layer -= 1 pre_layer = layer level.setdefault(layer, []).append(parent_node_dict) return [parent_node_dict] 

Источник

Python tree to list

I have a tree structure which I need to convert to a list of lists.
The class for a node is defined as (irrelevant detail removed):

class TMoveTree: # The nodes of the valid moves tree def __init__(self, parent, data): self._parent = parent self._children = [] self._data = data # a tuple (start, target)

The tree represents the valid moves for a board game. The game has three dice, so the maximum depth of the tree is 4 (1 level for the root node, and 1 for each die,) and each node can have up to 15 children. After generating and pruning the tree, I have a tree like below:

ROOT
|_____ (0, 3)
|_______ (0, 4)
| |_____ (0, 5)
| |_____ (3, 8)
| |_____ (4, 9)
|
|_______ (3, 7)
|_____ (0, 5)
|_____ (7, 12)

• Each branch should be a list of the tuples in that branch, ordered from leaf to root
• The lists generated from each branch are collected into a list, the order is irrelevant

I have the following function so far:

def tree2list(self): if len(self._children) == 0: return [self._data] else: node_list = [[self._data] + child.tree2list() for child in self._children] return node_list

Output:
[[(-1, -1), [(0, 3), [(0, 4), (0, 5)], [(0, 4), (3, 8)], [(0, 4), (4, 9)]], [(0, 3), [(3, 7), (0, 5)], [(3, 7), (7, 12)]]]]

How can I get my 'tree2list' function to output the desired list of lists?

Источник