The problem. Given an array preorder holding the pre-order walk (node, left subtree, right subtree) of a binary search tree with distinct values, rebuild the tree and return its root. A BST is fully determined by its pre-order.
preorder = [8, 5, 1, 7, 10, 12] -> [8, 5, 10, 1, 7, null, 12]
preorder = [1, 3] -> [1, null, 3]
preorder = [4, 2, 1, 3] -> [4, 2, null, 1, 3]Pre-order lists every parent before its children. So inserting the values one by one with plain BST insertion puts each node exactly where it was.
function bstFromPreorder(preorder) { const insert = (node, val) => { if (node === null) return new TreeNode(val); if (val < node.val) node.left = insert(node.left, val); else node.right = insert(node.right, val); return node; }; let root = null; for (const v of preorder) root = insert(root, v); return root;}Time O(n·h) — O(n²) for a skewed tree — space O(h).
Read the array left to right with a shared index. A call builds the subtree whose values are all below bound: if the next value is above the bound, this subtree is empty. Otherwise take it as the node, build its left subtree with bound = the node's value, and its right subtree with the parent's bound.
Each value is taken once; a value above the current bound means "this subtree is finished".
function bstFromPreorder(preorder) { let i = 0; const build = (bound) => { // the next subtree: values below bound if (i === preorder.length || preorder[i] > bound) return null; const node = new TreeNode(preorder[i++]); node.left = build(node.val); // smaller than this node node.right = build(bound); // bigger than it, but still below bound return node; }; return build(Infinity);}Time O(n), space O(h). Every value is read exactly once.
Walk the values with a stack of the current path. A value smaller than the top is the top's left child. A bigger value pops every node smaller than it — the last one popped is its parent, and it becomes that parent's right child.
function bstFromPreorder(preorder) { const root = new TreeNode(preorder[0]); const stack = [root]; for (let k = 1; k < preorder.length; k++) { const node = new TreeNode(preorder[k]); let parent = stack[stack.length - 1]; while (stack.length > 0 && stack[stack.length - 1].val < node.val) parent = stack.pop(); if (parent.val < node.val) parent.right = node; // the last smaller node popped else parent.left = node; // smaller than the top stack.push(node); } return root;}Time O(n) — each node is pushed and popped at most once — space O(h).
