Day 8: Construct Binary Tree from Preorder and Inorder Traversal

Problem Link:

Explore - LeetCode

Problem Statement:

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values
- Each value of inorder also appears in preorder
- preorder is guaranteed to be the preorder traversal of the tree
- inorder is guaranteed to be the inorder traversal of the tree

My Solution:

class Solution:
    def buildTree(self, P: List[int], I: List[int]) -> TreeNode:
        M = {I[i]: i for i in range(len(I))}
        return self.splitTree(P, I, M, 0, 0, len(P)-1)
    
    def splitTree(self, P: List[int], I: List[int], M: dict, pix: int, ileft: int, iright: int) -> TreeNode:
        rval = P[pix]
        root, imid = TreeNode(rval), M[rval]
        if imid > ileft:
            root.left = self.splitTree(P, I, M, pix+1, ileft, imid-1)
        if imid < iright:
            root.right = self.splitTree(P, I, M, pix+imid-ileft+1, imid+1, iright)
        return root

Explanation:

For this question, we can take advantage of the order of nodes in the traversals. A preorder traversal is [node, left, right] while an inorder traversal is [left, node, right].

We know that the root node for a tree is the first element of the preorder array (P). We also know that every element to the left of the root element in the inorder array (I) is on the left subtree, and everything to the right of the root element in I is on the right subtree.

Once you do that, your problem has now been reduced to a smaller set. Now you have the inorder and preorder traversal for the left and right subtree and you need to figure them out.

In order to make this work, we just need to pass left and right limits (ileft, iright) defining the subarray of the current subtree in I, as well as the index (pix) of the root node of the subtree in P.

At this point, we could iterate forward through I until we found out the location (imid) of the root node each time, but that would push this solution to time complexity of O(N²).

Instead, we can make a preliminary index map (M) of the values in I, so that we can look up the value for imid in O(1) time in each recursion. This will lower the time complexity to O(N) at the cost of a space complexity of O(N).

At each recursion, if imid = ileft, then there are no nodes to the left, so we shouldn’t call a recursion for that side. The same applies to the right side if imid = iright.

• Time Complexity: O(N) where N is the length of P and I
• Space Complexity: O(N) for M

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!