Construct a BST from preorder / validate a preorder sequence

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.