Binary Search Trees and Rebuilding a Tree
Think of a filing cabinet where every folder to the left of a given folder holds a smaller number, and every folder to the right holds a bigger one. That one rule, repeated at every level, is what turns a plain binary tree into a binary search tree (BST). It is a small rule with a big payoff: it makes search, insert, and delete run in O(log n) instead of O(n), and it opens up a whole family of "rebuild or validate this tree" interview problems.
The BST rule
For every node in a BST: everything in its left subtree is smaller than the node's value, and everything in its right subtree is bigger. That rule holds transitively across the whole subtree, not just against the immediate children. A common bug, covered below, comes from checking it only one level down.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = rightTake the tree built from inserting 5, 3, 8, 1, 4 in that order:
5
/ \
3 8
/ \
1 4Search, insert, and delete all cost O(h), where h is the tree's height. On a balanced tree that is O(log n), but on a degenerate tree, one built by inserting already-sorted data with no rebalancing, it collapses to a straight line and costs O(n). That's exactly why production databases and language runtimes use self-balancing trees (AVL, red-black) under the hood, even though building one yourself is outside interview scope.
Remember: left is always smaller, right is always bigger, at every level, not just the first. That single rule is the whole BST.
Why an inorder walk of a BST comes out sorted
Inorder visits left, then the node, then right. In a BST, left is always smaller and right is always bigger, so an inorder walk visits nodes in strictly increasing order. This one fact is the engine behind most BST-specific problems: find the kth smallest, check whether a tree is a valid BST, or turn a BST into a sorted list are all inorder traversal wearing a different name.
def inorder_values(root):
result = []
def visit(node):
if node is None:
return
visit(node.left)
result.append(node.val)
visit(node.right)
visit(root)
return resultRunning this on the 5, 3, 8, 1, 4 tree from above gives 1, 3, 4, 5, 8, in order, for free.
Remember: inorder of a BST is always sorted. If a problem mentions "kth smallest" or "sorted", think inorder first.
Inserting and searching
Both operations walk down from the root, comparing the target value at each node and choosing left or right, exactly the way you'd narrow down a phone book by comparing names.
def bst_insert(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
elif val > root.val:
root.right = bst_insert(root.right, val)
# val == root.val: no-op, assumes no duplicates
return root
def bst_search(root, val) -> bool:
if root is None:
return False
if val == root.val:
return True
return bst_search(root.left, val) if val < root.val else bst_search(root.right, val)Both run in O(h) time and O(h) space for the recursion stack. Written iteratively with a plain while loop instead of recursion, the space drops to O(1); mention that if asked to optimize space.
Remember: insert and search both just follow the BST rule downward: smaller goes left, bigger goes right, until you fall off the tree or find the value.
Rebuilding a tree from two traversals
Given two of the three DFS traversals, you can rebuild the exact original tree, but only certain pairs work.
- Preorder + inorder: works. Preorder's first element is always the root. Inorder tells you which values sit in the left subtree (everything before the root's position) and which sit in the right subtree (everything after).
- Postorder + inorder: also works, the mirror image: postorder's last element is the root.
- Preorder + postorder, with no inorder: does not uniquely rebuild the tree if any node has only one child, since there's no way to tell whether that lone child is a left or right child. It only works if every node has either 0 or 2 children.
- Preorder alone, or inorder alone: never enough. Many different trees can share the same single traversal.
This is exactly the kind of "why does this work but not that" follow-up interviewers ask once you've solved the reconstruction problem below, so know the reasoning, not just the code.
Remember: preorder or postorder tells you the root; inorder tells you how to split left from right. You need one of each.
Validate Binary Search Tree
Validate Binary Search Tree (LeetCode 98)
The tempting but wrong check is comparing each node only to its immediate children. That misses violations further down, like a left-subtree node that's bigger than an ancestor two levels up. The fix: carry a (low, high) range down through the recursion, and tighten it as you go.
Approach: Recursively validate each node against a (low, high) bound. Going left tightens high to the current node's value; going right tightens low.
def is_valid_bst(root) -> bool:
def validate(node, low, high):
if node is None:
return True
if not (low < node.val < high):
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root, float("-inf"), float("inf"))Complexity: Time O(n), space O(h) recursion stack.
Common mistakes:
- Checking only immediate children instead of carrying a range down. That passes trees which are locally fine but globally broken.
- An alternative correct approach: run an inorder traversal and check the result is strictly increasing. Also O(n)/O(h), and arguably simpler to reason about, though it can't stop early when an invalid tree is found near the root.
Remember: pass a shrinking (low, high) range down the recursion. A local left/right check alone is not enough.
Lowest Common Ancestor of a BST
Lowest Common Ancestor (LeetCode 235)
In a plain binary tree, finding the lowest common ancestor (LCA) needs a full traversal. A BST's ordering gives a shortcut: if both target values are smaller than the current node, the LCA must be in the left subtree; if both are bigger, it's in the right subtree. The moment they land on opposite sides, or one equals the current node, that node is the split point, and the LCA.
Approach: Walk down from the root using the BST-ordering shortcut, stopping as soon as p and q diverge (or one matches the current node).
def lowest_common_ancestor(root, p, q):
node = root
while node:
if p.val < node.val and q.val < node.val:
node = node.left
elif p.val > node.val and q.val > node.val:
node = node.right
else:
return node
return NoneComplexity: Time O(h), space O(1), since it's iterative with no recursion stack.
Common mistakes:
- Using a general-tree LCA algorithm (search both subtrees, O(n)) when the BST property gives an O(h) shortcut. Interviewers read this as missing the BST constraint.
- Getting the divergence condition backwards, or forgetting that when one of
p/qequals the current node, that node itself is the LCA.
Remember: both smaller means go left, both bigger means go right, otherwise you've found the split point, and that's the LCA.
Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Preorder and Inorder (LeetCode 105)
Preorder's first element is always the root. Find that value's position in inorder: everything to its left belongs to the left subtree, everything to its right belongs to the right subtree. Recurse on each side using the matching slices of both traversals.
Approach: Build a hash map from value to inorder index for O(1) lookups, instead of scanning inorder each time, which would make the naive version O(n²). Track a moving pointer into preorder, since each recursive call consumes exactly one preorder element, the current subtree's root, before recursing further.
def build_tree(preorder: list[int], inorder: list[int]):
inorder_index = {val: i for i, val in enumerate(inorder)}
self_preorder_idx = [0] # mutable pointer into preorder
def build(left, right):
if left > right:
return None
root_val = preorder[self_preorder_idx[0]]
self_preorder_idx[0] += 1
root = TreeNode(root_val)
mid = inorder_index[root_val]
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(inorder) - 1)Complexity: Time O(n), each node is processed once with an O(1) map lookup. Space O(n) for the map plus O(h) recursion stack.
Common mistakes:
- Using
inorder.index(root_val), a linear scan, instead of a precomputed hash map. That turns O(n) into O(n²). - Slicing lists (
preorder[1:mid+1]) instead of tracking indices. Correct, but it adds O(n) copying at every level, another hidden O(n²). - Forgetting to advance the preorder pointer before recursing left. The left subtree's preorder elements come right after the root, so building the right side before consuming the left side's elements corrupts the indices.
Remember: preorder's first element is the root; find it in inorder to split left from right; use a hash map, not a linear scan.
Kth Smallest Element in a BST
Kth Smallest Element in BST (LeetCode 230)
"Kth smallest" is exactly "the kth value visited during an inorder walk." No sorting needed; the BST's own structure hands you the order.
Approach: Do an inorder traversal, but stop the moment you've visited k elements. There's no need to build the full sorted list when k is small relative to n.
def kth_smallest(root, k: int) -> int:
stack = []
node = root
count = 0
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
count += 1
if count == k:
return node.val
node = node.right
raise ValueError("k is out of range")Complexity: Time O(h + k): descending to the leftmost node costs O(h), then visiting k more nodes, worst case O(n) if k is close to n. Space O(h) for the stack.
Common mistakes:
- Building the entire inorder list first, then indexing into it. Correct, but it wastes time and space when k is small, since there's no early exit.
- Off-by-one: k is usually 1-indexed, so return when
count == k, notcount == k - 1.
Remember: an iterative inorder walk that stops at count k, no need to build the full sorted list first.