Build a Binary Tree with Pre-order and In-order traversal data

Problem

Given a pre-order traversal array of integers and an in-order traversal array of integers, construct a binary tree.

Input

• preorder - array of integers
• inorder - array of integers

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

Approach

It is helpful to first jot down some observations:

• The first element in the pre-order array is the root value
• The middle element in the in-order array is NOT necessarily the root value
• The sub-array to the left and right of the root value in the in-order array are also in-order arrays for those sub-trees.

With these observations in mind, it is clear that a recursive approach is the best way to tackle this problem.

The key intuition here is to create sub-arrays out of preorder and inorder, where the sub-arrays represent smaller sub-trees.

Whenever we see a pre-order array, we can chop the first element out of that array and construct the root node from that element. The next question might be the following: how do we determine where the left and right children are?

We can take a step back here and take a look at the in-order array. Since we don't know where the root value is in this array, we'll have to find it by linearly iterating through it. Once we find the value, and ultimately the index of that value (call it \(i\), we can then see that the left sub-array has \(i - 1\) elements. This means that in the pre-order array, all we need to do is traverse right by \(i - 1\) to get to the pre-order sub-array for the right sub-tree.

Solution

def buildTree(self, preorder, inorder):  
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """

    def _build(preorder, inorder):
        if len(preorder) == 0 or len(inorder) == 0:
            return None

        root_val = preorder[0]
        root = TreeNode(root_val)

        i = inorder.index(root_val)

        root.left = _build(preorder[1:1+i], inorder[:i])
        root.right = _build(preorder[1+i:], inorder[i+1:])

        return root

    return _build(preorder, inorder)

This implementation is not the most optimal but it is perhaps one of the most easiest to read and understand. This is considered a brute-force algorithm since this is very heavy in space-complexity. Recursive calls will take up more space than iterative solutions (due to the call stack) and creating new sub-arrays inside each recursive call will take up even more space. Improvements can be made by implementing the function iteratively and to use indices to determine the left and right borders of the preorder and inorder arrays (similar to a binary tree search) instead of creating new sub-arrays.