Framework Thinking - Neetcode 150 - Construct Binary Tree from Preorder and Inorder Traversal

Here is solutions for Construct Binary Tree from Preorder and Inorder Traversal.

1. Understand the problem

You are given two arrays:
- preorder traversal of a binary tree
- inorder traversal of the same binary tree
Your task is to reconstruct the original binary tree and return its root.
Traversal properties:
- Preorder: Root → Left → Right
- Inorder: Left → Root → Right
You may assume:
- All node values are unique
- Both arrays describe a valid binary tree

2. Clarify constraints, asks 4 - 5 questions including edge cases.

Are all node values unique?

=> ✅ Yes (required for a unique reconstruction)

Can the tree be empty?

=> ✅ Yes, both arrays could be empty

What is the maximum size (n) of the tree?

=> Usually up to 10^4 (important for recursion depth & performance)

Are negative values allowed?

=> ✅ Yes, values can be any integer

Is the input guaranteed to be valid preorder & inorder of the same tree?

=> ✅ Yes

3. Explore examples.

Example 1:

preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

Tree:

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Naive Recursion - Time O(N^2), Space O(H)

Key Idea:

The first element of preorder is always the root.
Find this root in inorder.
Left subtree = elements left of root in inorder
Right subtree = elements right of root in inorder
Recursively repeat.

Drawback:

Finding root index in inorder costs O(n) every time → Total time O(N^2).
Time: O(N^2)
Space: O(H)

4.2. Solution 2 — Optimized with HashMap - Time O(N), Space O(N)

Use hashmap to store root.

{9:0, 3:1, 15:2, 20:3, 7:4}

Idea:

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

[9, 3, 15, 20, 7]
     ↑

Based on pre-order => root [3, 20]
        3
       / \
      9   20
         /  \
        15   7

Time: O(N)
Space: O(N)

5. Implement solutions.

5.1. Naive Solution - Depth First Search, Find Root from Preorder[0] to Inorder array - Time O(N^2), Space O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None

        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
        return root

Time: O(N^2)
Space: O(N)

5.2. Hash Map + Depth First Search - Time O(N), Space O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        indices = {val: idx for idx, val in enumerate(inorder)}

        self.pre_idx = 0
        def dfs(l, r):
            if l > r:
                return None

            root_val = preorder[self.pre_idx]
            self.pre_idx += 1
            root = TreeNode(root_val)
            mid = indices[root_val]
            root.left = dfs(l, mid - 1)
            root.right = dfs(mid + 1, r)
            return root

        return dfs(0, len(inorder) - 1)

Time: O(N)
Space: O(N)

5.3. Optimize DFS - Dynamic preIdx and inIdx so that do not traverse O(N) - Time O(N), Space O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        preIdx = inIdx = 0
        def dfs(limit):
            nonlocal preIdx, inIdx
            if preIdx >= len(preorder):
                return None
            if inorder[inIdx] == limit:
                inIdx += 1
                return None

            root = TreeNode(preorder[preIdx])
            preIdx += 1
            root.left = dfs(root.val)
            root.right = dfs(limit)
            return root
        return dfs(float('inf'))

Time: O(N)
Space: O(N)

5.4. Morris Traversal - Time O(N), Space O(1)

Key Idea:

Instead of backtracking store, point the leaf node into the recursion node address.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        head = TreeNode(None)
        curr = head
        i, j, n = 0, 0, len(preorder)
        while i < n and j < n:
            # Go right and then as far left as possible
            curr.right = TreeNode(preorder[i], right = curr.right)
            curr = curr.right
            i += 1
            while i < n and curr.val != inorder[j]:
                curr.left = TreeNode(preorder[i], right=curr)
                curr = curr.left
                i += 1
            j += 1
            while curr.right and j < n and curr.right.val == inorder[j]:
                prev = curr.right
                curr.right = None
                curr = prev
                j += 1

        return head.right

Time: O(N).
Space: O(1)

6. Dry run testcases.

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

Step	pre_idx	Root Val	Inorder Range	Mid	Left Range	Right Range
1	0 → 1	3	[0..4]	1	[0..0]	[2..4]
2	1 → 2	9	[0..0]	0	[]	[]
3	2 → 3	20	[2..4]	3	[2..2]	[4..4]
4	3 → 4	15	[2..2]	2	[]	[]
5	4 → 5	7	[4..4]	4	[]	[]

December 4, 2025