7.2 Binary Search Trees (BST)

1. What Is a Binary Search Tree (BST)?

In a plain Binary Tree, numbers can sit anywhere—so searching for 42 forces you to check every single node (O(N)).

A Binary Search Tree (BST) is a Binary Tree that obeys one strict ordering rule (the BST Invariant) at every single node X:

• Every node in X's entire left subtree is strictly smaller than X.val.
• Every node in X's entire right subtree is strictly larger than X.val.

2. Why Do We Need a BST & How Does It Work?

Look at the trade-off between Arrays and Linked Lists:

• Sorted Array: Searching is fast (O(log N) via Binary Search), but inserting a new item in the middle is slow (O(N) shifting).
• Linked List: Inserting is fast (O(1)), but searching is slow (O(N)).
• Balanced BST: Gives you both O(log N) searching and O(log N) insertion/deletion! At each node, you compare target with curr.val: if target < curr.val, you go left and throw away the entire right subtree—just like Binary Search!

Two Magic Properties of Every BST

1. Inorder Traversal (Left -> Root -> Right) of any BST visits the values in strictly sorted ascending order!
2. Range Validation Trap: When checking if a tree is a valid BST, checking left.val < node.val < right.val is not enough! You must pass down the allowed (min_val, max_val) boundaries so no deeper grandchild violates an ancestor's limit.

Bonus Operation: How Deleting a Node from a BST Works (3 Cases)

Interviewers love asking how deleteNode(root, key) maintains the BST property in O(H) time:

1. Case 1 (Target is a Leaf): Simply return null to detach it.
2. Case 2 (Target has Only 1 Child): Return its non-null child (root.left or root.right) to bypass the deleted node.
3. Case 3 (Target has 2 Children): Find its Inorder Successor (the smallest node in root.right — walk to root.right, then go .left as far as possible), copy that successor's value into root.val, and recursively delete the successor from root.right!

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Search for target in a BST -> O(log N) balanced, O(H) general
def search_bst(root, target: int):
  curr = root
  while curr:
      if curr.val == target:
          return curr
      elif target < curr.val:
          curr = curr.left
      else:
          curr = curr.right
  return None

# 2. Insert a value into a BST -> O(log N) balanced
def insert_into_bst(root, val: int):
  if not root:
      return TreeNode(val)
  if val < root.val:
      root.left = insert_into_bst(root.left, val)
  else:
      root.right = insert_into_bst(root.right, val)
  return root

# 3. Validate BST using (low, high) range boundaries -> O(N)
def is_valid_bst(root, low=float("-inf"), high=float("inf")) -> bool:
  if not root:
      return True
  if not (low < root.val < high):
      return False
  return (
      is_valid_bst(root.left, low, root.val)
      and is_valid_bst(root.right, root.val, high)
  )

4. Core Interview Patterns & Common Traps

# Kth Smallest in BST (Iterative Inorder Stack -> stops at k!):
stack = []
curr = root
while curr or stack:
  while curr:
      stack.append(curr)
      curr = curr.left
  curr = stack.pop()
  k -= 1
  if k == 0:
      return curr.val
  curr = curr.right

5. Practice On Your Own (Curated Submodule Problems)