Construct Binary Tree from Preorder and Inorder Traversal

The problem description can be found in LeetCode.

Approach

As usual, we have to derive some examples to really understand how to solve a problem.

If we see the first one in the problem description, we can notice that:

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

The first 3 will be the actual root node in the tree and we can find it in the preorder list.

Then, if we look for the node 3 in the inorder list, we can notice that the elements on the:

• left are part of the left subtree ([9]).
• right are part of the right subtree ([15, 20, 7]).

If we apply the same logic again recursively, we can see that this also applies to all the other nodes.

We can apply such properties to the code too.

Solution

from typing import List, Optional


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        assert len(preorder) == len(inorder)

        if not preorder:
            return None

        val = preorder[0]
        node = TreeNode(val)
        n = inorder.index(val)

        node.left = self.buildTree(preorder[1 : n + 1], inorder[:n])
        node.right = self.buildTree(preorder[n + 1 :], inorder[n + 1 :])

        return node

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the number of nodes in the tree