☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Construct a BST from a preorder traversal

Medium TUF ID 101 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array preorder of distinct integers that is the preorder traversal (node, then left subtree, then right subtree) of some binary search tree. Build that BST and return its root.

The answer is unique. The first key of a preorder is the root; the keys smaller than it are exactly the left subtree and the keys larger than it are the right subtree, and the same argument applies recursively inside each part. Constraints (LeetCode): 1 ≤ n ≤ 100, keys distinct. The code below also accepts an empty array and returns an empty tree.

Trees are shown in LeetCode level order, with null for a missing child.

Example 1

preorder = [8, 5, 1, 7, 10, 12]

        8
       / \
      5   10
     / \    \
    1   7    12

answer = [8, 5, 10, 1, 7, null, 12]

8 is the root; 5, 1, 7 are smaller, so they form the left subtree; 10, 12 form the right subtree.

Example 2

preorder = [1, 3]
answer = [1, null, 3]     // 3 > 1, so it can only be the right child

Approach 1: Brute force, insert one key at a time

Intuition. The simplest way to build a BST is ordinary insertion: start with an empty tree and insert the keys in the given order. The surprising part is that inserting in preorder order reproduces exactly the target tree. Preorder lists every node before its descendants, so when a key is inserted, all of its ancestors in the target tree are already present. Insertion walks down by comparing with those ancestors, which are precisely the comparisons that define where the key belongs, so it lands in its correct slot.

Algorithm.

  1. Start with root = null.
  2. For each key v in preorder, walk from the root: go left if v is smaller than the current key, right otherwise, until the needed child is empty.
  3. Attach a new node for v there.
static TreeNode bruteForce(int[] preorder) {
    TreeNode root = null;
    for (int v : preorder) root = insert(root, v);
    return root;
}

static TreeNode insert(TreeNode root, int v) {
    TreeNode node = new TreeNode(v);
    if (root == null) return node;
    TreeNode cur = root;
    while (true) {
        if (v < cur.val) {
            if (cur.left == null) { cur.left = node; break; }
            cur = cur.left;
        } else {
            if (cur.right == null) { cur.right = node; break; }
            cur = cur.right;
        }
    }
    return root;
}

Complexity. Time O(n^2) in the worst case. Each insertion costs O(h), and for sorted input such as [1, 2, 3, 4, 5] the tree is a chain, so the i-th insertion walks i nodes. For a random-looking preorder the tree is balanced and it is O(n log n). Space O(1) beyond the tree itself, because insertion is iterative.

Approach 2: Better, preorder plus inorder

Intuition. The in-order traversal of any BST is just its keys in sorted order. So we can manufacture the inorder by sorting a copy of the preorder, and then use the standard “construct a binary tree from preorder and inorder” technique. The next preorder key is always the root of the current subtree; its position mid in the inorder splits the remaining keys into the left part [lo, mid - 1] and the right part [mid + 1, hi]. A hash map from key to inorder index makes each split O(1).

The preorder index is shared across all calls (here, a one-element array next), because preorder lists the entire left subtree before the right subtree, which is exactly the order in which the recursion consumes keys.

Algorithm.

  1. Copy and sort preorder to get inorder; map each key to its index.
  2. buildRange(lo, hi): if lo > hi, return null. Otherwise take the next preorder key v, find mid = pos[v].
  3. Build the left child from [lo, mid - 1], then the right child from [mid + 1, hi].
static TreeNode better(int[] preorder) {
    int[] inorder = preorder.clone();
    Arrays.sort(inorder);
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
    int[] next = {0};                                    // index of the next preorder key to place
    return buildRange(preorder, pos, next, 0, inorder.length - 1);
}

static TreeNode buildRange(int[] preorder, Map<Integer, Integer> pos, int[] next, int lo, int hi) {
    if (lo > hi) return null;                            // no keys belong to this subtree
    int v = preorder[next[0]++];
    TreeNode node = new TreeNode(v);
    int mid = pos.get(v);                                // keys left of mid go left, right of mid go right
    node.left = buildRange(preorder, pos, next, lo, mid - 1);
    node.right = buildRange(preorder, pos, next, mid + 1, hi);
    return node;
}

Complexity. Time O(n log n) for the sort; the construction itself is O(n). Space O(n) for the sorted copy and the map, plus O(h) for recursion.

Approach 3: Optimal, consume the preorder with an upper bound

Intuition. The sort and the map exist only to answer one question: “does the next preorder key still belong to the subtree I am building?” We can answer that with a bound instead. While building the left subtree of a node with key v, every key must be below v; the first key above v means the left subtree is complete. While building the right subtree of v, keys must be below whatever bound v itself had to respect (the key of the nearest ancestor whose left subtree contains v).

Why is no lower bound needed? Suppose we are building the right subtree of v and the next key is smaller than v. In a valid preorder that key would have to belong to v’s left subtree, which has already been finished and passed in the sequence. That cannot happen, so checking the upper bound alone is enough.

Algorithm.

  1. Keep a shared index next into preorder, starting at 0.
  2. buildWithBound(bound): if all keys are used or preorder[next] > bound, return null.
  3. Otherwise create a node from preorder[next] and advance next.
  4. Build its left child with bound node.val and its right child with the inherited bound.
static TreeNode optimal(int[] preorder) {
    int[] next = {0};
    return buildWithBound(preorder, next, Long.MAX_VALUE);
}

static TreeNode buildWithBound(int[] preorder, int[] next, long bound) {
    if (next[0] == preorder.length || preorder[next[0]] > bound) return null;
    TreeNode node = new TreeNode(preorder[next[0]++]);
    node.left = buildWithBound(preorder, next, node.val);    // left keys must stay below node.val
    node.right = buildWithBound(preorder, next, bound);      // right keys inherit the parent's bound
    return node;
}

Dry run on [8, 5, 1, 7, 10, 12]:

call bound next key action
root +∞ 8 create 8
left of 8 8 5 create 5
left of 5 5 1 create 1
left of 1 1 7 7 > 1, null
right of 1 5 7 7 > 5, null
right of 5 8 7 create 7
left of 7 7 10 10 > 7, null
right of 7 8 10 10 > 8, null
right of 8 +∞ 10 create 10
left of 10 10 12 12 > 10, null
right of 10 +∞ 12 create 12
children of 12 12 / +∞ none left null, null

Complexity. Time O(n): every call either creates a node (n times) or returns null immediately (at most n + 1 times, one per empty child slot). Space O(h) for the recursion.

The bound is a long starting at Long.MAX_VALUE, so a key equal to Integer.MAX_VALUE is accepted at the top level. The tests include [0, Integer.MIN_VALUE, Integer.MAX_VALUE].

An equivalent iterative version uses a stack: push each new key; if it is smaller than the stack top it becomes that node’s left child, otherwise pop while the top is smaller and attach it as the right child of the last popped node. It is also O(n) and avoids recursion, but the bound version shows the reasoning more directly.

Edge cases and pitfalls