Construct Binary Tree from Preorder and Inorder Traversal medium

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 binary 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] Input: [-1]

Steps and Explanation

The core idea behind solving this problem is leveraging the properties of preorder and inorder traversals.

Preorder traversal: Root, Left Subtree, Right Subtree Inorder traversal: Left Subtree, Root, Right Subtree

1. Find the Root: The first element in preorder is always the root of the tree.

2. Divide and Conquer: Locate the root in inorder. The elements to the left of the root in inorder form the left subtree's inorder traversal, and the elements to the right form the right subtree's inorder traversal.

3. Recursive Construction: The same number of elements to the left of the root in inorder will also exist in preorder, starting from the second element. These elements constitute the preorder traversal for the left subtree. Similarly, the remaining elements in preorder form the preorder traversal for the right subtree.

4. Base Case: The recursion stops when a sub-array is empty (no more nodes to process).

5. Node Construction: For each subtree, recursively call the function to construct the left and right subtrees. Once the left and right subtrees are built, create a new node with the current root and attach the subtrees.

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val; }
 * }
 */
class Solution {
    private Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndexInInorder = inorderMap.get(rootVal);

        int leftSubtreeSize = rootIndexInInorder - inStart;

        root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, rootIndexInInorder - 1);
        root.right = buildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, rootIndexInInorder + 1, inEnd);

        return root;
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because each node is visited once during the recursive construction.
• Space Complexity: O(N) in the worst case. This is due to the recursive call stack (depth of the recursion can be N in a skewed tree) and the inorderMap which stores N entries. In the average case, the space complexity will be O(log N) for a balanced tree.