Construct Binary Search Tree from Preorder Traversal

Medium
1938.

Construct Binary Search Tree from Preorder Traversal

Construct Binary Search Tree from Preorder Traversal is a medium coding problem on arrays, binary search and trees, asked in Amazon, Microsoft and Meta interviews.

You are given an array preorder of distinct integers that is the preorder traversal of a binary search tree — each node listed before its left subtree, which comes before its right subtree. Rebuild the tree and return its root.

In a binary search tree every value in a node's left subtree is strictly smaller than the node's value, and every value in its right subtree is strictly larger. It is guaranteed that preorder describes such a tree, and that tree is unique.

Example 1

Input
preorder = [8,5,1,7,10,12]
Output
[8,5,10,1,7,null,12]
Explanation
8 is the root; 5, 1, 7 are smaller and form its left subtree (5 with children 1 and 7); 10, 12 are larger and form the right subtree.

Example 2

Input
preorder = [1,3]
Output
[1,null,3]
Explanation
3 is larger than the root, so it is the root's right child.

Example 3

Input
preorder = [3,2,1]
Output
[3,2,null,1]
Explanation
Each value is smaller than the one before it, so the tree is a chain going left.

Constraints

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 1000
  • All the values of preorder are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function(preorder) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct Binary Search Tree from Preorder Traversal Solution

Construct Binary Search Tree from Preorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Construct Binary Search Tree from Preorder Traversal is a medium coding problem on arrays, binary search and trees, asked in Amazon, Microsoft and Meta interviews.

Problem statement

You are given an array preorder of distinct integers that is the preorder traversal of a binary search tree — each node listed before its left subtree, which comes before its right subtree. Rebuild the tree and return its root.

In a binary search tree every value in a node's left subtree is strictly smaller than the node's value, and every value in its right subtree is strictly larger. It is guaranteed that preorder describes such a tree, and that tree is unique.

Example 1

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Explanation: 8 is the root; 5, 1, 7 are smaller and form its left subtree (5 with children 1 and 7); 10, 12 are larger and form the right subtree.

Example 2

Input: preorder = [1,3]
Output: [1,null,3]
Explanation: 3 is larger than the root, so it is the root's right child.

Example 3

Input: preorder = [3,2,1]
Output: [3,2,null,1]
Explanation: Each value is smaller than the one before it, so the tree is a chain going left.

Constraints

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 1000
  • All the values of preorder are unique

Hints for Construct Binary Search Tree from Preorder Traversal

  1. Hint 1

    The first value is the root. The values after it that are smaller form the left subtree's preorder, and the rest the right subtree's.

  2. Hint 2

    Splitting by scanning for the first larger value is O(n^2) on a chain. Instead, build while reading: pass down an upper bound for the current subtree.

  3. Hint 3

    build(bound): if the next value exceeds bound, this subtree is empty. Otherwise take it as the node, build its left subtree with the bound node.val, then its right subtree with the inherited bound.

How to solve Construct Binary Search Tree from Preorder Traversal

Read the preorder array once with a shared index. Each recursive call builds the largest subtree whose values stay below an upper bound; the bound tells it exactly when its subtree has ended, so no searching is needed.

Approach

  1. Keep an index i = 0 into preorder.
  2. build(bound): if i is past the end or preorder[i] > bound, return null.
  3. Otherwise create a node with preorder[i], advance i, set left = build(node.val) and right = build(bound), and return the node.
  4. Return build(+infinity) (the largest 32-bit integer works).

Why it works

In preorder, a node is followed first by all of its left subtree (values below it) and then by its right subtree (values above it but below the bound inherited from the nearest ancestor it hangs left of). The first value that breaks the bound is therefore the first value outside the current subtree, so each call consumes exactly its subtree's values.

Complexity

  • Time — O(n) — every value is consumed once
  • Space — O(h) for the recursion

Pitfalls

  • The left subtree's bound is the node's value; the right subtree inherits the parent's bound, not the node's value.
  • Keep the index shared across calls (a field, a reference or a one-element array), not a copy.
  • Inserting each value from the root also works but is O(n^2) on a sorted input.

Reference solution

Python

from typing import List, Optional

def bstFromPreorder(preorder: List[int]) -> Optional[TreeNode]:
    i = 0

    def build(bound):
        nonlocal i
        if i == len(preorder) or preorder[i] > bound:
            return None
        node = TreeNode(preorder[i])
        i += 1
        node.left = build(node.val)
        node.right = build(bound)
        return node

    return build(float("inf"))

Java

public static TreeNode bstFromPreorder(int[] preorder) {
    return build(preorder, new int[1], Integer.MAX_VALUE);
}

static TreeNode build(int[] pre, int[] i, int bound) {
    if (i[0] == pre.length || pre[i[0]] > bound) return null;
    TreeNode node = new TreeNode(pre[i[0]++]);
    node.left = build(pre, i, node.val);
    node.right = build(pre, i, bound);
    return node;
}

C++

TreeNode* buildBounded(vector<int>& pre, int& i, int bound);

TreeNode* bstFromPreorder(vector<int>& preorder) {
    int i = 0;
    return buildBounded(preorder, i, INT_MAX);
}

TreeNode* buildBounded(vector<int>& pre, int& i, int bound) {
    if (i == (int) pre.size() || pre[i] > bound) return nullptr;
    TreeNode* node = new TreeNode(pre[i++]);
    node->left = buildBounded(pre, i, node->val);
    node->right = buildBounded(pre, i, bound);
    return node;
}

JavaScript

var bstFromPreorder = function(preorder) {
    var i = 0;
    var build = function(bound) {
        if (i === preorder.length || preorder[i] > bound) return null;
        var node = new TreeNode(preorder[i++]);
        node.left = build(node.val);
        node.right = build(bound);
        return node;
    };
    return build(Infinity);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search