Q13: How do you reconstruct a Binary Tree from Preorder and Inorder traversal arrays?

Preorder traversal determines the root node (first element). Inorder traversal splits the tree into left and right subtrees relative to the root node position. Map inorder values to indices using a HashMap<Integer, Integer> for $O(1)$ lookup, and construct the tree recursively.

Tree Construction from Preorder & Inorder

import java.util.HashMap;
import java.util.Map;

public class BuildTree {
    private static int preIndex = 0;
    private static final Map<Integer, Integer> inMap = new HashMap<>();

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        preIndex = 0;
        inMap.clear();
        for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
        return helper(preorder, 0, inorder.length - 1);
    }
    private static TreeNode helper(int[] preorder, int left, int right) {
        if (left > right) return null;
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        int inIndex = inMap.get(rootVal);
        root.left = helper(preorder, left, inIndex - 1);
        root.right = helper(preorder, inIndex + 1, right);
        return root;
    }
}

💡 Identifies root nodes using preorder indexing and partitions subtrees using inorder index bounds.

Key Takeaways

Preorder gives root values sequentially.
Inorder index map determines left/right subtree element boundaries.

Knowledge Check

Why is an index lookup HashMap constructed for the inorder array elements?

Q13: How do you reconstruct a Binary Tree from Preorder and Inorder traversal arrays?

STAY UPDATED WITH BYTES!