Construct a BST from preorder / validate a preorder sequence
Problem
(1) Build the BST whose preorder traversal is the given array. (2) Given an array, return true if it could be the preorder traversal of some BST.
Example 1
Input: build from [8, 5, 1, 7, 10, 12] Output: [8, 5, 10, 1, 7, null, 12]
Example 2
Input: valid? [2, 4, 1] Output: false
Also asked as: Construct BST from preorder traversal · Check preorder is valid or not
Test cases
Case 1
Input: [8,5,1,7,10,12] Expected: [8,5,10,1,7,null,12]
Case 2
Input: [3,2,1] Expected: [3,2,null,1]
Case 3
Input: [1,2,3] Expected: [1,null,2,null,3]
Case 4
Input: [1] Expected: [1]
View solutionHide solution1 approach
1. Bounds recursion
Time O(n)Space O(h)
Consume preorder values while they fit the current (low, high) bound; the first value becomes the root, then recurse left with an updated upper bound and right with a lower bound.
function bstFromPreorder(preorder) { let i = 0; const 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);}Validate a preorder: use a stack; pop while the current value exceeds the stack top (that becomes the new lower bound). If any value is below the current lower bound, it is invalid.