Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 105 | Difficulty: Medium

Medium

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]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

- `1 <= preorder.length <= 3000`

- `inorder.length == preorder.length`

- `-3000 <= preorder[i], inorder[i] <= 3000`

- `preorder` and `inorder` consist of **unique** values.

- Each value of `inorder` also appears in `preorder`.

- `preorder` is **guaranteed** to be the preorder traversal of the tree.

- `inorder` is **guaranteed** to be the inorder traversal of the tree.

Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 104 ms)

Metric	Value
Runtime	104 ms
Memory	N/A
Date	2018-05-20

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        if (preorder.Length == 0) return null;
    Stack<TreeNode> s = new Stack<TreeNode>();
    TreeNode root = new TreeNode(preorder[0]), cur = root;
    for (int i = 1, j = 0; i < preorder.Length; i++)
    {
        if (cur.val != inorder[j])
        {
            cur.left = new TreeNode(preorder[i]);
            s.Push(cur);
            cur = cur.left;
        }
        else
        {
            j++;
            while (s.Count!=0 && s.Peek().val == inorder[j])
            {
                cur = s.Pop();
                j++;
            }
            cur = cur.right = new TreeNode(preorder[i]);
        }
    }
    return root;
    }
}

📜 3 more C# submission(s)

Submission (2018-05-18) — 112 ms, N/A

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        if (preorder.Length == 0) return null;
    Stack<TreeNode> s = new Stack<TreeNode>();
    TreeNode root = new TreeNode(preorder[0]), cur = root;
    for (int i = 1, j = 0; i < preorder.Length; i++)
    {
        if (cur.val != inorder[j])
        {
            cur.left = new TreeNode(preorder[i]);
            s.Push(cur);
            cur = cur.left;
        }
        else
        {
            j++;
            while (s.Count!=0 && s.Peek().val == inorder[j])
            {
                cur = s.Pop();
                j++;
            }
            cur = cur.right = new TreeNode(preorder[i]);
        }
    }
    return root;
    }
}

Submission (2018-05-20) — 128 ms, N/A

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        return BuildTreeInPre(inorder, 0, inorder.Length-1, preorder, 0);
    
}

public TreeNode BuildTreeInPre(int[] inOrder, int ins, int ie, int[] preorder, int ps)
{
    if (ins > ie) return null;
    TreeNode root = new TreeNode(preorder[ps]);
    int index = Array.IndexOf(inOrder, preorder[ps]);
    root.left = BuildTreeInPre(inOrder, ins, index - 1, preorder, ps+1);
    root.right = BuildTreeInPre(inOrder, index + 1, ie, preorder, ps + index - ins+1);
    return root;
}
}

Submission (2018-05-20) — 128 ms, N/A

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        return BuildTreeInPre(inorder, 0, inorder.Length-1, preorder, 0);
    
}

public TreeNode BuildTreeInPre(int[] inOrder, int ins, int ie, int[] preorder, int ps)
{
    if (ins > ie) return null;
    TreeNode root = new TreeNode(preorder[ps]);
    int index = Array.IndexOf(inOrder, preorder[ps]);
    root.left = BuildTreeInPre(inOrder, ins, index - 1, preorder, ps+1);
    root.right = BuildTreeInPre(inOrder, index + 1, ie, preorder, ps + index - ins+1);
    return root;
}
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Hash map gives O(1) lookup — think about what to use as key vs value.