Construct BST from Preorder Traversal Hard 0 attempts
GeeksforGeeks ↗

Construct BST from Preorder Traversal

Hard TreeBinary TreeDFS GeeksforGeeks

You're given an array preorder representing the preorder traversal of a binary search tree. Build that BST and return its root.

Input Format
Implement bstFromPreorder(preorder). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Returned trees are displayed as level-order arrays, trimming trailing nulls.

Sample Input and Output

Example 1 ยท Run Sample

Input
preorder = [8,5,1,7,10,12]
Output
[8,5,10,1,7,null,12]

Example 2

Input
preorder = [1]
Output
[1]
Constraints
  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 10^8
  • All values are unique
Test Cases (2)
Case 1
Args: [[8,5,1,7,10,12]] Expected: [8,5,10,1,7,null,12]
Case 2
Args: [[1]] Expected: [1]
Topics
TreeBinary TreeDFS

Recursive with Bound

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

javascript
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