Construct Binary Tree from Preorder and Inorder Traversal

Share

Given two integer arrays preorder and inorder where preorder is the preorder traversal 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]

Solution Approach

The first element of preorder is always the root. Find its position in inorder; elements to its left form the left subtree, right form the right subtree. Recurse.

  • preIndex = 0 (global counter).
  • Find root = preorder[preIndex++] in inorder using a HashMap for O(1) lookup.
  • Elements at inorder[0..mid-1] are left subtree, inorder[mid+1..] are right subtree.
  • Recurse: build left subtree, then right subtree.
Java
import java.util.*;

class Solution {
    int preIdx = 0;
    Map<Integer, Integer> inMap = new HashMap<>();

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

    private TreeNode build(int[] preorder, int lo, int hi) {
        if (lo > hi) return null;
        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);
        int mid = inMap.get(rootVal);
        root.left = build(preorder, lo, mid - 1);
        root.right = build(preorder, mid + 1, hi);
        return root;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)