Construct BST from Preorder Traversal Hard 0 attempts
GeeksforGeeks ↗

Construct BST from Preorder Traversal

Hard TreeBinary TreeDFS GeeksforGeeks

Given a preorder traversal of a BST, construct the BST.

Example: preorder = [8,5,1,7,10,12] → Output: BST with root 8

Sample Input
—
Sample Output
—
Constraints
  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 10^8
  • All values are unique
Topics
TreeBinary TreeDFS

Recursive with Bound

Use an upper bound to determine when to stop building the left subtree.

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

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript