Problem Description

You are given an array of integers called preorder that represents the preorder traversal of a Binary Search Tree (BST). Your task is to reconstruct the original BST from this traversal and return the root of the tree.

Key Concepts:

Binary Search Tree (BST): A binary tree where for every node:

• All nodes in the left subtree have values strictly less than the node's value
• All nodes in the right subtree have values strictly greater than the node's value

Preorder Traversal: A way of visiting nodes in a tree following this order:

1. Visit the current node (root) first
2. Traverse the left subtree
3. Traverse the right subtree

For example, if you have a BST:

      8
     / \
    5   10
   / \    \
  1   7   12

The preorder traversal would be: [8, 5, 1, 7, 10, 12]

Your Goal: Given the preorder traversal array, reconstruct the original BST structure and return its root node.

Important Note: The problem guarantees that there will always be a valid BST that can be constructed from the given preorder traversal for all test cases.

Intuition

When we have a preorder traversal of a BST, we know that the first element is always the root. But how do we figure out which elements belong to the left subtree and which belong to the right subtree?

The key insight comes from the BST property: all values in the left subtree are less than the root, and all values in the right subtree are greater than the root.

Since we're dealing with a preorder traversal (root → left → right), after the root element, we'll encounter all the left subtree elements first, followed by all the right subtree elements. This means:

• Elements smaller than the root come first (these form the left subtree)
• Elements larger than the root come after (these form the right subtree)

For example, with [8, 5, 1, 7, 10, 12]:

• Root is 8
• Elements less than 8: [5, 1, 7] (left subtree)
• Elements greater than 8: [10, 12] (right subtree)

To find the boundary between left and right subtrees, we need to find the first element that's greater than the root. Everything before this boundary belongs to the left subtree, and everything from this point onwards belongs to the right subtree.

Since the array maintains the relative order from the preorder traversal, we can use binary search to efficiently find this boundary point. Why binary search? Because once we encounter an element greater than the root, all subsequent elements in the right subtree will also be greater than the root (due to the preorder nature).

Once we identify the left and right subtree ranges, we can recursively apply the same logic:

• Build the left subtree from its range
• Build the right subtree from its range
• Connect them to the root

This divide-and-conquer approach naturally leads to a recursive solution where each recursive call handles a specific range of the preorder array, constructing its corresponding subtree.

Learn more about Stack, Tree, Binary Search Tree, Binary Tree and Monotonic Stack patterns.

Solution Approach

The solution uses a Divide and Conquer approach with Binary Search to efficiently construct the BST from the preorder traversal.

Implementation Details:

We define a recursive function dfs(i, j) that constructs a BST from elements in the range preorder[i] to preorder[j].

Step-by-step breakdown:

1. Base Case: If i > j, the range is invalid, so we return None (empty subtree).

2. Create Root Node: The first element preorder[i] in our current range is always the root of the current subtree.

   root = TreeNode(preorder[i])

3. Find the Split Point Using Binary Search: We need to find where the left subtree ends and the right subtree begins. This is the first element greater than preorder[i].

   We use binary search on the range [i+1, j+1):

   l, r = i + 1, j + 1
   while l < r:
       mid = (l + r) >> 1  # equivalent to (l + r) // 2
       if preorder[mid] > preorder[i]:
           r = mid  # element is too large, search left half
       else:
           l = mid + 1  # element is small, search right half

   After the binary search, l points to the first element greater than preorder[i], which is the start of the right subtree.

4. Recursive Construction:

   • Left subtree: Contains elements from i+1 to l-1 (all elements less than root)

     root.left = dfs(i + 1, l - 1)

   • Right subtree: Contains elements from l to j (all elements greater than root)

     root.right = dfs(l, j)

5. Return the constructed tree: Return the root node with its connected subtrees.

Time Complexity: O(n log n) where n is the number of nodes. For each of the n nodes, we perform a binary search that takes O(log n) time in the worst case.

Space Complexity: O(n) for the recursion stack in the worst case (skewed tree).

Example Walkthrough with [8, 5, 1, 7, 10, 12]:

• First call: dfs(0, 5), root = 8
  • Binary search finds index 4 (value 10 is first > 8)
  • Left subtree: dfs(1, 3) → processes [5, 1, 7]
  • Right subtree: dfs(4, 5) → processes [10, 12]
• The process continues recursively for each subtree until the complete BST is constructed.

Example Walkthrough

Let's walk through constructing a BST from the preorder traversal [8, 5, 1, 7, 10, 12].

Initial Call: dfs(0, 5) - Processing entire array

• Root value: preorder[0] = 8
• Create root node with value 8
• Binary search for split point (first element > 8):
  • Search range: indices 1 to 5
  • Check middle (index 3): preorder[3] = 7 < 8, search right half
  • Check middle (index 4): preorder[4] = 10 > 8, found split!
  • Split point: index 4

Left Subtree: dfs(1, 3) - Processing [5, 1, 7]

• Root value: preorder[1] = 5
• Create node with value 5
• Binary search for split point (first element > 5):
  • Search range: indices 2 to 3
  • Check middle (index 2): preorder[2] = 1 < 5, search right half
  • Check index 3: preorder[3] = 7 > 5, found split!
  • Split point: index 3

Left-Left Subtree: dfs(2, 2) - Processing [1]

• Root value: preorder[2] = 1
• Create node with value 1
• Binary search finds no split (single element)
• Both children are null (base case reached)

Left-Right Subtree: dfs(3, 3) - Processing [7]

• Root value: preorder[3] = 7
• Create node with value 7
• Binary search finds no split (single element)
• Both children are null (base case reached)

Right Subtree: dfs(4, 5) - Processing [10, 12]

• Root value: preorder[4] = 10
• Create node with value 10
• Binary search for split point (first element > 10):
  • Search range: index 5
  • Check index 5: preorder[5] = 12 > 10, found split!
  • Split point: index 5

Right-Right Subtree: dfs(5, 5) - Processing [12]

• Root value: preorder[5] = 12
• Create node with value 12
• Both children are null (base case reached)

Final BST Structure:

      8
     / \
    5   10
   / \    \
  1   7   12

The algorithm correctly reconstructs the BST by:

1. Using the first element as the root
2. Finding the boundary between left and right subtrees using binary search
3. Recursively building each subtree with the same approach

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm uses a divide-and-conquer approach with binary search. For each node in the BST:

• The dfs function is called once for each of the n nodes in the preorder array
• Within each dfs call, a binary search is performed to find the partition point between left and right subtrees
• The binary search takes O(log k) time where k is the size of the current subarray
• In the worst case (balanced tree), the binary search at the root level examines n elements, at the next level each of two calls examines n/2 elements, and so on
• This gives us a recurrence relation: T(n) = 2T(n/2) + O(log n)
• By the Master Theorem, this resolves to O(n × log n)

Space Complexity: O(n)

The space complexity consists of:

• The recursion call stack depth, which is O(h) where h is the height of the tree
• In the worst case (skewed tree), the height can be O(n)
• In the best case (balanced tree), the height would be O(log n)
• The tree nodes themselves require O(n) space to store all n values
• Therefore, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Boundary for Finding the Split Point

The Pitfall: A common mistake is setting up the binary search incorrectly when finding where the right subtree begins. Developers often use wrong initial boundaries or update logic:

# INCORRECT: Using wrong right boundary
l, r = i + 1, j  # Should be j + 1, not j
while l < r:
    mid = (l + r) // 2
    if preorder[mid] > preorder[i]:
        r = mid
    else:
        l = mid + 1

This error causes the binary search to miss the last element in the range, potentially placing nodes in the wrong subtree.

Why This Happens:

• Confusion about whether to use inclusive or exclusive boundaries
• Not accounting for the case where all remaining elements belong to the left subtree (no right subtree exists)

The Solution: Always use j + 1 as the right boundary to ensure the search can correctly identify when all remaining elements are less than the root (meaning no right subtree):

# CORRECT: Proper boundary setup
l, r = i + 1, j + 1  # j + 1 allows us to handle case where no right subtree exists

2. Off-by-One Errors in Recursive Calls

The Pitfall: Incorrectly calculating the ranges for left and right subtree recursive calls:

# INCORRECT: Wrong range calculations
root.left = dfs(i + 1, l)      # Should be l - 1, not l
root.right = dfs(l + 1, j)     # Should be l, not l + 1

Why This Happens:

• Misunderstanding what l represents after binary search (it's the first element of the right subtree)
• Confusion about inclusive vs exclusive indices

The Solution: Remember that after binary search, l points to the first element greater than root (start of right subtree):

• Left subtree: from i + 1 to l - 1 (all elements less than root)
• Right subtree: from l to j (all elements greater than root)

# CORRECT: Proper range calculations
root.left = dfs(i + 1, l - 1)  # Elements before the split point
root.right = dfs(l, j)          # Elements from split point onwards

3. Not Handling Edge Cases in Binary Search

The Pitfall: Failing to handle the case where there's no left or right subtree:

# PROBLEMATIC: Doesn't handle edge cases well
if i == j:  # Only one element
    return TreeNode(preorder[i])
# What if all elements after root are smaller? Or all are larger?

The Solution: The binary search approach with j + 1 as the right boundary naturally handles these cases:

• If no right subtree exists, l will equal j + 1 after binary search
• If no left subtree exists, l will equal i + 1 after binary search
• The recursive calls with these boundaries will hit the base case i > j and return None

This elegant handling of edge cases is why the boundary setup r = j + 1 is crucial for correctness.