Binary tree from given Inorder and Preorder traversal 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 "&lt;TreeNode&gt;"


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:


How can I structure the code to reduce the cognitive overload (I was literally stuck juggling with all those variables)?
How can I debug these kinds of recursive calls?
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.