Preorder to BST | Practice Medium 0 attempts
GeeksforGeeks ↗

Preorder to BST | Practice

Medium TreeBinary TreeDFS GeeksforGeeks

You're given the preorder traversal of a binary search tree. Reconstruct the original BST from it.

Input Format
Implement preorderToBST(pre). 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
pre = [8,5,1,7,10,12]
Output
[8,5,10,1,7,null,12]

Example 2

Input
pre = [1]
Output
[1]
Constraints
  • 1 <= N <= 10^3
  • 1 <= pre[i] <= 10^4
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 Upper Bound

javascript
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