Algorithm-Day48-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal-lc-105

Posted on In , Views:

🧩 Problem Description

Given two integer arrays preorder and inorder where:

  • preorder is the preorder traversal of a binary tree
  • inorder is the inorder traversal of the same tree

Construct and return the binary tree.

💬 Example

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

💡 Approach: DFS + HashMap for Index Lookup

Key Observations:

  1. In preorder traversal, the first element is always the root.
  2. In inorder traversal, elements to the left of root belong to the left subtree, and elements to the right belong to the right subtree.
  3. We can use a HashMap to store value → index mappings in inorder array for O(1) splits.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private Map<Integer, Integer> inorderIndexMap;
    private int preorderIndex;

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

    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;

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

        int inorderIndex = inorderIndexMap.get(rootVal);

        root.left = build(preorder, left, inorderIndex - 1);
        root.right = build(preorder, inorderIndex + 1, right);

        return root;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — each node is created once, and index lookup is O(1).
  • Space Complexity: O(n) — for recursion stack and hashmap.

✍️ Summary

  • This is a classic divide and conquer problem.
  • Preorder gives root order, inorder gives subtree boundaries.
  • Related problems:
    • lc-106 — Construct from Inorder and Postorder
    • lc-889 — Construct from Preorder and Postorder