Problem Statement in English

You’re given the inorder and preorder traversal of a binary tree as lists. You need to reconstruct the binary tree using these 2 lists.

Approach

Here’s the thing with preorder, inorder and postorder traversals.

  • Preorder traversal’s leftmost element is the first root.
  • Postorder traversal’s rightmost element is the first root.
  • The elements on the left of the root you identified from the preorder or postorder traversal form the left subtree of that node, and the elements on the right of the node form the right subtree of the node.

That probably sounds really messed up, but that’s ok, we’ll look at an example and you’ll be fine. Just keep in mind, that to reconstruct the binary tree you MUST have the inorder and either the preorder or postorder traversal. The inorder helps identify elements in the subtree, and the preorder or postorder provide us a root to work with in that subtree.

Let’s say we have the following inorder and preorder traversals: inorder: [9,3,15,20,7] preorder: [3,9,20,15,7]

Let’s reconstruct the tree by hand, just to get a feel for it:

  • We know that the leftmost element of the preorder is the first root. Thus the root of the tree is 3.
  • Now we look at the inorder traversal to figure out the contents of the left and right subtrees. Elements in the left subtree are [3], and elements in the right subtree are [15,20,7].
  • Clearly, there’s only one element in the left subtree, [3].
  • Now let’s look at the right subtree. How do we figure out the root from those elements? We find the leftmost of those 3 in the preorder list: 20.
  • 20 is the root of the right subtree of 3. Now let’s check the inorder list to find elements in the left subtree and right subtree, that we’ve not processed previously. [15,7].
  • 15 is on the left of 20 in the inorder list, and 7 is on the right. Hence, 15 is the left child of 20, and 7 is the right child.

That’s it. If we connect all these pieces together, we get the required tree.

Solution in Python

Full disclosure: this is not my code, I got this online from NeetCode (brilliant channel by the way, definitely check him out).

I couldn’t implement this on my own, and everytime I tried, it got needlessly complicated. I figured it was best I stopped wasting so much time insisting on doing it myself, and just learn how to do it instead. I think it was a good choice. This code is really elegant, readable…and…I really like it.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # checks if either preorder or inorder is empty 
        if not preorder or not inorder:
            # if so, return None
            return None

        # the leftmost root of preorder is the current root
        root = TreeNode(preorder[0])

        # finds the index of the root in the inorder list
        mid = inorder.index(preorder[0])

        # to build the left subtree
        root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
        # to build the right subtree
        root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])

        # returns the consolidated root at each step, with its children
        return root

1. To build the left subtree:

root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
  • Which part of inorder do we use for this subproblem?

All elements to the left of the index occupied by the root in the inorder list (we’re calling that index mid). So that’s indices in the range $[0,mid)$ within inorder.

  • Which part of preorder do we use for this subproblem?

Starting index (inclusive): 1, since we want to start from after the root of this tree, which is at index 0. Ending index (exclusive): mid+1, since we want to include indices until mid. So that’s indices in the range $[1,mid]$ within preorder.

2. Same thing for the right subtree:

Complexity

  • Time: $O(n^2)$
    This is because we’re having to search within the inorder to find the index of the root for every element in preorder.

I think this can be improved by adding a lookup table; so we run through the inorder once, and store each element as a key, and have its index as the value. That will definitely increase the space complexity, but there will have to be a tradeoff.

  • Space: $O(n)$
    Since we’re using a recursion stack. We’re also making copies of the lists to each recursive function call, but in Big O notation it shouldn’t matter.

Mistakes I Made

You kidding me? I had to look this one up. I knew how to solve it on paper, but transferring it into code was just terrible. I botched the implementation every time I tried it. I’ve spent days on this problem.

In all fairness, I feel this is a hard problem rather than the medium that it’s tagged as. I know the solution makes it look super easy, but coming up with the algorithm on your own is…I don’t know how viable, especially in an interview. But if you know how to do it - you know the concept, it’s not that bad.

And we are done.