1008. Construct Binary Search Tree from Preorder Traversal

Problem Statement

Pattern: Related: 98. Validate BST

---

Ranged Solution

From 98. Validate BST

int i = 0;
 
private TreeNode validate(int[] pre, int min, int max) {
	if(i >= pre.length || pre[i] < min || pre[i] > max) return null;
	
	TreeNode root = new TreeNode(pre[i++]);
	root.left = validate(pre, min, root.val);
	root.right = validate(pre, root.val, max);
	
	return root;
}
 
public TreeNode bstFromPreorder(int[] preorder) {
	return validate(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

int i = 0;
public TreeNode bstFromPreorder(int[] A) {
	return bstFromPreorder(A, Integer.MAX_VALUE);
}
 
public TreeNode bstFromPreorder(int[] A, int max) {
	if (i == A.length || A[i] > bound) return null;
	TreeNode root = new TreeNode(A[i++]);
	root.left = bstFromPreorder(A, root.val);
	root.right = bstFromPreorder(A, max);
	return root;
}

you dont need lower bound since it is preorder so lower bound will alwys be true

Iterative Solution

public TreeNode bstFromPreorder(int[] pre) {
	Deque<TreeNode> stack = new LinkedList<>();
	TreeNode root = new TreeNode(pre[0]), node;
	stack.push(root);
	for(int i = 1; i < pre.length; i++) {
		node = new TreeNode(pre[i]);
		if(pre[i] < stack.peek().val) {
			stack.peek().left = node; 
		} else {
			TreeNode parent = stack.peek();
			while (!stack.isEmpty() && pre[i] > stack.peek().val) 
				parent = stack.pop();
			parent.right = node;
		}
		stack.push(node);
	}
	return root;
}