Binary tree from given Inorder and Preorder traversal

Question

This builds a BinaryTree from given Inorder and Preorder lists.

class TreeNode(object):
  """Node of a Binary tree."""
  def __init__(self, key, left=None, right=None):
      self.key = key
      self.left = left
      self.right = right

  def __str__(self):
    return "{0}".format(self.key)

  def __repr__(self):
    return "<TreeNode>"


def insert_left(parent, node):
  parent.left = node
  return parent


def insert_right(parent, node):
  parent.right = node
  return parent


def level_order(node):
  """Given Binary Tree gives list nodes in each level."""
  if node is None:
    return
  current_level = [node]
  res = []
  while current_level:
    res.append(current_level)
    next_level = []
    for node in current_level:
      if node.left:
        next_level.append(node.left)
      if node.right:
        next_level.append(node.right)
    current_level = next_level
  return res


def build_tree(inorder, preorder):
  """Builds a Binary Tree from given inorder and preorder traversal.
  Steps:
    1. Take the first element from the preorder list.
    2. Get the index of the element from inorder list.
    3. Set the element as root.
    4. Take all elements left to root from inorder list.
    5. Take all elements right to root from inorder list.
    6. Calculate preorder list for left and right subtree respectively.
    7. Repeat from step 1 for each subtree.
  """
  def recurse(node, inorder, preorder):
    if len(preorder) == 1:
      return TreeNode(preorder)
    key  = preorder[0]
    root_index    = inorder.find(key)
    inorder_left  = inorder[:root_index]
    inorder_right = inorder[root_index+1:]
    preorder_left = preorder[1:len(inorder_left)+1]
    preorder_right = preorder[root_index+1:]
    node = TreeNode(key)
    if len(inorder_left):
      insert_left(node, recurse(None, inorder_left, preorder_left))
    if len(inorder_right):
      insert_right(node, recurse(None, inorder_right, preorder_right))
    return node
  return recurse(None, inorder, preorder)


import unittest

class TestBinaryTree(unittest.TestCase):
  def setUp(self):
    self.root = build_tree('DBEAFC', 'ABDECF')

  def test_build_tree(self):
    expected = [['A'], ['B', 'C'], ['D', 'E', 'F']]
    actual = []
    for level in level_order(self.root):
      actual.append([node.key for node in level ])
    self.assertEqual(actual, expected)


if __name__ == '__main__':
  unittest.main()

Output

A
B C
D E F

Although the code passes given test case I have to shamefully admit that it took me nearly the whole day to figure out the recursive build_tree method. I had a hard time to debug my recursive code by pen and paper as I was unable to track the progress of each recursive call (hope I could use version control and show the code progress). Anyway, as a last resort I started putting random code here and there finally putting None in this call insert_left(node, recurse(None, inorder_left, preorder_left)) worked.

So, I am here with some fundamental questions:

1. How can I structure the code to reduce the cognitive overload (I was literally stuck juggling with all those variables)?

2. How can I debug these kinds of recursive calls?

Answer 1

Here are some thoughts of mine regarding the binary tree implemenation, some ways to handle your questions and my actual implementation with some more comments.

My thoughts on binary tree implementation

Intrigued by your multiple posts regarding binary trees in different variations I've spent the day implementing my own version of a BinaryTree. The main issues I've seen overall in your code, which was the focus for my reimplementation are the following:

• Simplify the build of the tree – Your code slices and dices the double list of a preorder and inorder list of values. This seems like a vaste of space and time, so I aimed for a version doing a single pass on the list, whilst maintaining the possibility to create an arbitrary tree (i.e. out of order if so wanted :-) ). This lead to the need for a better serialization of the binary tree, where "https://stackoverflow.com/questions/2675756/efficient-array-storage-for-binary-tree/" sums up some of the logic I'm using

  Added: When reviewing both yours, Barrys and my own solution I came to wonder why do you have node as a parameter at all in your recurse() code? It is not used as a parameter, but is always set to a new value and could be a local variable. This would simplify your calling structure, and if you then allow for empty trees to enter you'll see that your code is quite similar to that which Barry has made (although he has skipped the intermediate storage of the sliced lists)

• Simplify order traversals using yields – Not exactly in this code, but some of the other questions you have made some rather complicated order traversals, which can be much neater given the nature of binary trees and the use of the yield operator. So I did some of those...
• Introduce an equality operator for the binary trees – When testing it is nice to compare the trees, and there exists at least three ways to do this. First option that the trees are identical with same address references, which I find not so useful. Secondly, to compare that the binary trees have the same structure and the same values across the trees. Thirdly, that the binary trees holds the same values in the same order, but not that the trees them selves are identical. I implemented the latter two in the code below.

Your questions

Structuring of code is, and will always be a bit of a challenge, but finding good, simple and nice solution are a part of it. That is, do research to find algorithms which matches what you want to accomplish, and do not be afraid of tossing away earlier attempts at solving the problem at hand.

If your code gets to complicated, or has to many variables (not neatly connected), then you most likely need to rethink your solution or modularisation. A function should have one concern or responsibility, and that task it should do very well.

In other words, one way to handle structure of code is to break it down into small pieces, and then reassemble these pieces into something which works. And if you find yourself doing copy-and-paste of code, seriously think about using functions or making a common function.

Regarding how to debug recursive functions, I tend to fall back to loads of debug output. In this particular case I did some changes to the binary structure to help me identify where I was. In addition to storing key, left and right, I also incremented a class counter to act as a unique identifier for each and every node I created. This in addition with a simple print(self) sprinkled around, made it a lot easier to debug.

My __str__ therefore looks like this:

 def __str__(self):
    return "BinaryTree - node id: {}, value:  {}, left: {}, right: {}".format(
            self._node_number,
            self.value,
            self.left._node_number if self.left else BinaryTree.nil_marker,
            self.right._node_number if self.right else BinaryTree.nil_marker,
          )

I'll come back to the nil_marker, which currently defaults to . as most of the testing was done with text strings as in your examples. However when I tested my class using integers, I change it to None.

This implementation of __str__ gives me a full output of relevant information regarding a given node on one line, and is good help to look into the logic of the method I'm debugging.

My implementation

The code with tests stands currently at over 300 lines, so I'll just post parts of it (and will most likely use some other parts in other responses in due time). I've focused on the initialization, in order and pre order traversal, and finally on the building of the tree with some testing in a separate code segment below.

from collections import deque
from itertools import izip_longest

class BinaryTree(object):
    """Structure to hold a binary tree, for starters based on letter nodes."""

    # Next two variables are used as default for the traversal
    # methods to indicate if left or right equal to None should
    # yield the nil_marker value. This is needed in order to
    # produce exact representation when doing pre- or postorder traversal
    yield_none_values = False
    nil_marker = '.'

    # When yielding none values, this is used as yield value within
    # the level order traversal
    level_shift_marker = ':'

    # _node_count is an internal counter and identificator for how many
    # BinaryTree nodes has been created. Used when outputting the nodes
    # in the __str__ method to connect nodes
    _node_count = 0

    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

        # Assign identifier to the node, and a loose count of nodes
        BinaryTree._node_count += 1
        self._node_number = BinaryTree._node_count

    # def __str__: as above

     def __eq__(self, other):
        """Check if both trees exists, and have same value and subtrees."""

        # Return early if only one of the tree exists
        #   or if only one of them has a right tree
        #   or if only one of them has a left tree
        if (bool(self) ^ bool(other)
            or (bool(self.right) ^ bool(other.right))
            or (bool(self.left) ^ bool(other.left))):

            return False

        # Otherwise compare the values, and that sub trees are equal
        return (self.value == other.value
                and self.right == other.right
                and self.left == other.left)


    def __ne__(self, other):
        """Negated version of BinaryTree.__eq__"""
        return not self.__eq__(other)


    def values_in_order(self):
        """Yield the inorder traversal of the binary tree."""

        if self.left:
            for value in self.left.values_in_order():
                yield value

        yield self.value

        if self.right:
            for node in self.right.values_in_order():
                yield node


    def values_pre_order(self, 
                         yield_none_values = yield_none_values,
                         nil_marker=nil_marker):
        """Yield the pre order traversal of the binary tree."""

        yield self.value

        if self.left:
            for value in self.left.values_pre_order(yield_none_values, nil_marker):
                yield value
        # used to get a marker when self.left is None
        elif yield_none_values:
            yield nil_marker

        if self.right:
            for node in self.right.values_pre_order(yield_none_values, nil_marker):
                yield node
        # used to get a marker when self.right is None
        elif yield_none_values:
            yield nil_marker


    @classmethod
    def from_preordered_list(cls, preordered_list, nil_marker=nil_marker):
        """Recreate binary tree from preordered list with nil markers.

        Builds a complete binary tree based on a preordered traversal text
        where missing left or right subtrees are marked with the nil marker.
        """    
        def decode():
            """Decodes the list into a binary tree.

            For each call it decodes at most three element, one for the node
            value, and two more for the left and right subtree.
            """
            if node_list:
                node_val = node_list.popleft()

            else:
                return None

            if node_val != nil_marker:
                node_left = decode()
                node_right = decode()
                node =  BinaryTree(node_val, node_left, node_right)
                return node
            else:
                return None

        node_list = deque(preordered_list)
        return decode()

Regarding traversal methods

Notice how neat the values_in_order() and values_pre_order() gets when you can rely on the yield operator to return at the proper timing. The values_post_order() is equally simply, with just a move of the yield self.value to the end of the method. Usually, you couls also remove the elif in the values_pre_order() method, but I left it in so you can see how I got to generate the preorder text strings used in the test code below.

Regarding __eq__

In this definition of the binary tree to be equal I require that the structure of the binary tree is equal as well as the value of the nodes. In order to check for equality without too much hassle of None pointers I use a trick to simplify the if (self and not other) or (not self and other) test into if bool(self) ^ bool(other). The latter uses the exclusive or operator to verify that either are both positive or both are negative. Also see "https://stackoverflow.com/questions/432842/how-do-you-get-the-logical-xor-of-two-variables-in-python"

Later on I test self.right == other.right, which triggers a recursion of the equality operator down the trees, if they are not both None already where it doesn't have to recurse to find the equality.

Another version of equality can be achieved using the in order traversal, and comparing value for value whilst tagging along using itertools.izip_longest to join the iterations of both the trees to be compared.

Some binary trees and preorder text version of those

I'm not sure if the following block will help or confuse, but here are some examples of trees I've used when testing presented in beatiful ascii art, and followed by the preorder traversal string later used for composition of the tree and another notation (level no: value, left tree, right tree) is used recursively. Note how the nil corresponds to the . marker in, and that it goes depth first to traverse and a find a full tree.

Some binary trees:

       D           D    D                    G
     /   \        /      \               /     \
   B       F     B .    . F            C         H
  / \     /     /          \          /  \        \
 A   C   E     A . ..  .. . G        B     F    .  I
complete      left       right     /     /
                                  A  .  D   .       ..
                                         \
. denotes some of the empty nodes      .  E 
                                       strange


Balanced tree: DBA..C..FE... -> (0: D, (1: B, (3: A, nil, nil), (3: C, nil, nil)), (2: F, (3: E, nil, nil), nil))  
Left tree: DBA....  -> (0: D, (1: B, (2: A, nil, nil), nil), nil)  
Right tree: D.F.G.. -> (0: D, nil, (1: F, nil, (2: G, nil, nil)))  
Strange tree: GCBA...FD.E...H.I.. -> 
 (0:G, 
   (1: C, 
      (2: B, 
         (3: A, nil, nil),
          nil),
      (2: F, 
         (3: D,
             nil, 
            (4: E, nil, nil)),
          nil),
   (1: H,
       nil,
      (2: I, nil, nil)

PS! I see now that Barry has added another answer, that your test tree has the preorder text of ABD..E..CF as you've based your example on the level order sequence, whilst my balanced tree is based upon the in order sequence...

Some test code to finish it off

Here is some of the test code I've used, where I append all the trees I'm making into an array for later printing and comparison. I could definitive make the test cases neater, but it is getting late...

def string_join(join_list, join_text=''):
    return join_text.join(str(i) for i in join_list)


def main():

    trees = []
    trees.append(('balanced',
                   BinaryTree('D', 
                     BinaryTree('B', 
                       BinaryTree('A'),
                       BinaryTree('C')),
                     BinaryTree('F',
                       BinaryTree('E')))))

    trees.append(('balanced_DEC', 
                  BinaryTree.from_preordered_list('DBA..C..FE')))
    trees.append(('integer_tree', 
                  BinaryTree.from_preordered_list([4, 2, 1, None, None, 
                                                   3, None, None, 6, 5], None)))

    trees.append(('strange_tree',
                   BinaryTree('G',
                     BinaryTree('C',
                       BinaryTree('B',
                         BinaryTree('A')),
                       BinaryTree('F',
                         BinaryTree('D',
                           None,
                           BinaryTree('E')))),
                     BinaryTree('H',
                       None,
                       BinaryTree('I')))))

    trees.append(('strange_tree_vDecoded',
                  BinaryTree.from_preordered_list('GCBA...FD.E...H.I')))
    print

    previous_tree = None

    for tree_name, tree in trees:

        print('Tree name: {}'.format(tree_name))
        print('  Equal to previous tree: {}'.format(previous_tree == tree))
        print('  Pre order: {}'.format(string_join(tree.values_pre_order(yield_none_values = True))))
        print('  In order: {}'.format(string_join(tree.values_in_order())))

        print
        previous_tree = tree


if __name__ == '__main__':
    main()

As can be seen in the output below, the manually built and decoded version of the trees are equal, and the implementation can also be used for a binary tree of integers, or whatever list you'll want.

Tree name: balanced
  Equal to previous tree: False
  Pre order: DBA..C..FE...
  In order: ABCDEF

Tree name: balanced_DEC
  Equal to previous tree: True
  Pre order: DBA..C..FE...
  In order: ABCDEF

Tree name: integer_tree
  Equal to previous tree: False
  Pre order: 421..3..65...
  In order: 123456

Tree name: strange_tree
  Equal to previous tree: False
  Pre order: GCBA...FD.E...H.I..
  In order: ABCDEFGHI

Tree name: strange_tree_vDecoded
  Equal to previous tree: True
  Pre order: GCBA...FD.E...H.I..
  In order: ABCDEFGHI

So, to finish off, this is my take on implementing the binary tree in a class, and using a somewhat simpler mechanism to build an arbitrary tree. Hope you get something useful out of it, at least I'm learning a lot doing reviews here on Code Review SE.

Addendum 1: Non-broken __repr__

Caridorc mention in his answer that your implementation of __repr__ doesn't work, well, here is one which does work according to my tests (even though it could possibly handle the None cases better...) :

def __repr__(self):
   """Return a string which when eval'ed will rebuild tree"""

   return '{}({}, {}, {})'.format(
             self.__class__.__name__,
             repr(self.value),
             repr(self.left) if self.left else None,
             repr(self.right) if self.right else None) \
                  .replace(', None, None)', ')') \
                  .replace(', None)', ')')

Answer 2

Recursive Code Should Be Recursive

Making build_tree recursive makes perfect sense. After all, pretty much everything you're going to do with trees is recursive, and this algorithm definitely lends itself well to recursion. However, your function isn't recursive. It calls a recursive function, and recurse takes a node - which obfusticates the algorithm. It would be much easier to understand if you just made it recursive - this goes a long way "to reduce the cognitive overload."

Let's start with the base case - if we have no ordering, we have no tree:

def build_tree(inorder, preorder):
    if not inorder:
        return None
    else:
        ### ??

Now, your enumerated steps for recursion seem to overcomplicate the algorithm. We want to go top-down! Given your example, when we start with:

in:  DBEAFC
pre: ABDECF

What's the root? A. The first element of pre-traversal is the root. Now we just need to find the left and right subtrees. To find that, we need to break up our in orderings into the root, left, and right sections:

in:  DBE|A|FC

So we have 3 nodes less than A and two nodes greater than A. We use the same sizes for the preorder:

pre: A|BDE|CF

And then recurse on those two parts. That is:

def build_tree(inorder, preorder):
    if not inorder:
        return None
    else:
        idx = inorder.index(preorder[0])
        return TreeNode(preorder[0],
                left=build_tree(inorder[:idx], preorder[1:idx+1]),
                right=build_tree(inorder[idx+1:], preorder[idx+1:])
                )

As a truly recursive solution, divided neatly into base and recursive cases, I find it much easier to follow the logic.

Debugging

Rather than write a level-by-level comparison, you should simply write an __eq__ method on TreeNode (or, alternatively, a much more correct __str__ or __repr__), and then use that to compare:

self.assertEqual(
    build_tree('DBEAFC', 'ABDECF'),
    TreeNode('A',
        TreeNode('B', TreeNode('D'), TreeNode('E')),
        TreeNode('C', TreeNode('F'))))

This is a more direct comparison. As is, you're comparing the levels, but there's not one unique tree that has three levels 'A', 'BC', and 'DEF'. For instance, what if your code erroneously returned one of these:

     A        |        A
   /   \      |     /    \
  B     C     |    B      C
 / \     \    |     \    / \
D   E     F   |      D  E   F

You'd think you succeeded. Always compare directly against what you want to get.

Answer 3

__repr__ is broken

It is a convention that you really should follow that eval(x.__repr__) == x but you return a simple string that evalled cannot give an object back.

TreeNode should be a namedtuple

After further inspection, treenode really does not need to be a class, but is better off as a namedtuple, that as a bonus is immutable as it should be, because I see no benefit in changing a node.

Simplifying build_tree

recurse is not needed, by clever using of default arguments you can write it as a single function (and make it easier to understand).

To lighten cognitive load

Test everything, your test is a step in the right direction, but it tests just one function, you should test all of them.

Answer 4

Edited: This is more of an addendum to the other answers, trying to give some base for the alternate versions of build_tree and referencing some more authoritative resources for the various approaches. As such it might seem a little off topic when read out of context.

Serialization and deserialization of binary trees

Or a somewhat authoritative guide on storing and recreating binary trees. After doing some searches on the title above, there seem to be consensus on the following three alternatives for saving binary trees:

• Save as an array where the \$i\$'th node has its children at indices \$2i + 1\$ (for the left child) and \$2i +2\$ (for the right child). See https://en.wikipedia.org/wiki/Binary_tree#Arrays
• Save both the inorder and preorder traversal, and recreate based on these. Note that only one of them will not be enough, as that has multiple tree versions available, when we're talking about generic binary trees. See http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
• Save the preorder traversal with markers for either internal/external nodes, or markers for None pointers. See http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/

In the solutions provided so far, CodeYogi and Barry's revision thereof, are using the inorder and preorder variant, whilst Holroy's solution is using the preorder with nil markers.

Nobody uses the array method, so far, and that is possibly related to the fact that the array method is very effective for storing a complete tree, but it is a little more complicated to rebuild and usually it would waste some space storing a non-complete tree.

Storage space considerations

A quote from the previous link (http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/):

How to store a general Binary Tree?

A simple solution is to store both Inorder and Preorder traversals. This solution requires space twice the size of Binary Tree.

We can save space by storing Preorder traversal and a marker for NULL pointers.

When using the inorder and preorder method, you are effectively storing \$2n\$ elements. Using the preorder with nil-markers, you are storing \$n + m\$ where \$m\$ is the number of nil-markers. Number of nil-markers varies but is in the same magnitude as \$n\$. However since nil-markers can possibly be stored in less space than the actual data, it is usually less demanding on storage space.

And if you got to a case where the actual data element has multiple of bytes, i.e. an int or text strings, the nil-marker could still be only one byte (or even 1 bit if you go to a binary storage format). In short your saving a bit of space.

Recreating a binary tree in code

For test purposes and code development it is useful to be able to recreate a binary tree to a given representation, as this allows to test various algorithms and methods. If we used more of a default filler the shape of the tree can be unknown, albeit the inorder sequence should be identical. But for now let's consider some various ways to recreate a tree in code.

The binary tree we're rebuilding is the binary tree from OP's original question:

     A        inorder, preorder: DBEAFC, ABDECF
   /   \      preorder with nil-marker: ABD..E..CF
  B     C     array: ABCDEF.
 / \   /
D   E F

Using inorder and preorder

Typical code example:

letter_tree = build_tree('DBEAFC', 'ABDECF')
integer_tree = build_tree([4, 2, 5, 1, 6, 3], [1, 2, 4, 5, 3, 6])
# The integer_tree works in Barry's version, but not with CodeYogi

Some pros and cons:

• You'll have to provide two version of the array, but both can easily be found using debug print output
• When rebuilding you'll have to slice and dice the inorder and preorder list, to build corresponding subtrees
• Depending on how you slice and dice, you might have a (minor) memory issue if you push all the sub-lists on the call stack
• As you need to refind an element from the inorder list in the preorder list, and then divide the lists the time efficiency will be \$O(n^2)\$

Using preorder with nil-markers

Typical code example:

letter_tree = build_tree('ABD..E..CF')
integer_tree = build_tree([1, 2, 4, None, None, 5, None, None, 3, 6])

Some pros and cons:

• Albeith you'll only need one string/list, you'll still need to get it from a debug print output
• The traversal is \$O(n)\$, as you loop the list only once during building of the tree
• No extra memory involved besides the original list and the final tree

Manually build of the tree

Two variants typically exists to do a manual build of a binary tree:

# Recursive initialization
letter_tree = TreeNode('A',
                TreeNode('B',
                  TreeNode('D'), 
                  TreeNode('E')
                ),
                TreeNode('C',
                  Treenode('F')
                )
              )

# Using left/right variables
integer_tree = TreeNode(1)
integer_tree.left = TreeNode(2)
integer_tree.right = TreeNode(3)
integer_tree.left.left = TreeNode(4)
integer_tree.left.right = TreeNode(5)
integer_tree.right.left = TreeNode(6)

Some pros and cons:

• This is the no fuzz method, as you build the tree directly, but it is kind of hard to follow the tree build, and easy to go wrong
• In some implementation, you might not be able to access the childs directly either
• It tends to be quite verbose, and building a large tree is advised against

Using an array

Typical code example:

root = build_tree('ABCDEF.')

Some pros and cons:

• Not quite sure about this one, as I haven't coded it for quite some years, but memory wise it should be quite efficient as it only has the one list
• However the implementation must either require some fancy index arithmetic or heavy traversal
• Assuming some fancy index arithmetic you should be able to make an algorithm with time complexity \$O(n)\$ since you can pre-calculate the height of the tree based on the length of the input array, and then do a full traversal of the 'non-existing' tree and filling in the blanks as you go. (You could even chose to store your binary tree as a binary heap, in which case the transformation is \$O(1)\$ )

Is there a conclusion to be made?

Not really, as it kind of depends on your needs and what values you want to store in your binary tree, and whether you are going to de-/serialize the tree often. Both inorder&preorder and preorder with nil-markers can be made to accomodate different value types (as proven by me and Barry).

Still I'm leaning towards the preorder with nil-markers, as it has a nice implementation, slightly lower storage costs, and accomodates different value types easily. And I kind of favour only to have to build one list before calling my build routine, instead of two.