LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

An Interactive Visual Explainer

Idea By: Chetan Pachpande | Executed By: Gemini

Back to Home

Problem Description

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]

Explanation: The binary tree is constructed as follows:

     3
   /   \
  9     20
       /  \
      15   7

Complexity Analysis

Time Complexity: O(N)
We visit each node once. The HashMap lookup for the inorder index is O(1).

Space Complexity: O(N)
O(N) for the HashMap and O(H) for the recursion stack, where H is the height of the tree. In the worst case (a skewed tree), H can be N.

Java Solution

class Solution {
    private int preorderIndex = 0;
    private HashMap<Integer, Integer> inorderMap;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Build HashMap for O(1) inorder index lookup
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        
        return buildTreeHelper(preorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTreeHelper(int[] preorder, int left, int right) {
        if (left > right) {
            return null;  // Base case: empty subtree
        }
        
        // Get root value from preorder
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        
        // Find root position in inorder
        int rootIndex = inorderMap.get(rootVal);
        
        // Build left and right subtrees
        root.left = buildTreeHelper(preorder, left, rootIndex - 1);
        root.right = buildTreeHelper(preorder, rootIndex + 1, right);
        
        return root;
    }
}

Intuition

This problem leverages the unique properties of **preorder** and **inorder** traversals to reconstruct a binary tree.

  1. Preorder Logic: The first element is always the root of the current subtree.
  2. Inorder Split: Find the root in inorder traversal to determine left and right subtree boundaries.
  3. Recursive Construction: Use these boundaries to recursively build left and right subtrees.
  4. HashMap Optimization: Store inorder indices in a HashMap for O(1) lookups instead of O(N) searches.

Step-by-Step Code

Live Visualization

Preorder Array:

Inorder Array:

Algorithm States

Status: Idle Preorder Index: N/A Current Range: N/A Root Value: N/A Root Inorder Index: N/A

Call Stack

Stack is empty

Execution Commands