Preorder to BST | Practice Medium 0 attempts
GeeksforGeeks ↗

Preorder to BST | Practice

Medium TreeBinary TreeDFS GeeksforGeeks

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

Example: pre = [40,30,35,80,100] → BST with root 40

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^3
  • 1 <= pre[i] <= 10^4
Topics
TreeBinary TreeDFS

Recursive with Upper Bound

function preorderToBST(pre) {
  let i = 0;
  function build(bound) {
    if (i >= pre.length || pre[i] > bound) return null;
    const node = {val: pre[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