Binary Search Trees

1. 1.Search in a Binary Search Tree
   Iterative loop: target < val -> go Left, target > val -> go Right in O(H) timeeasy
2. 2.Validate Binary Search Tree
   Carry ancestor bounds: minVal < node.Val < maxVal down the recursionmedium
3. 3.Kth Smallest Element in a BST
   Inorder traversal yields sorted values: return Kth visited nodemedium
4. 4.Lowest Common Ancestor of a BST
   If p & q < node -> go Left; if both > node -> go Right; else current node is split point LCA!medium
5. 5.Insert into a Binary Search Tree
   Search for target position until nil, then attach new nodemedium
6. 6.Delete Node in a BST
   3 cases: Leaf (remove), 1 child (replace), 2 children (replace with Inorder Successor = min of right subtree)medium
7. 7.Convert Sorted Array to Binary Search Tree
   Choose middle element as root recursively: nums[mid] is rooteasy
8. 8.Minimum Absolute Difference in BST
   Inorder traversal yields sorted values: track min diff between adjacent elementseasy
9. 9.Two Sum IV — Input is a BST
   Inorder to sorted array + Two Pointers, or HashSet during DFSeasy
10. 10.Range Sum of BST
    Prune search: skip Left if node.Val < low, skip Right if node.Val > higheasy
11. 11.BST Iterator
    Controlled Inorder DFS using stack: push all left nodes initiallymedium
12. 12.Recover Binary Search Tree
    Inorder DFS detecting swapped adjacent / non-adjacent nodesmedium
13. 13.Trim a Binary Search Tree
    If node.Val < low return trim(Right); if node.Val > high return trim(Left)medium
14. 14.Balance a Binary Search Tree
    Inorder to sorted array + construct balanced BST from middlemedium
15. 15.Convert BST to Greater Tree
    Reverse Inorder (Right -> Root -> Left) maintaining running summedium
16. 16.Construct BST from Preorder Traversal
    Pass upper bound down recursion or use monotonic stackmedium

1. 17.Find Mode in Binary Search Tree
   Inorder traversal tracking current count & max count without extra memoryeasy
2. 18.Increasing Order Search Tree
   Inorder DFS rewiring right pointers (Left = nil)easy
3. 19.Closest Binary Search Tree Value
   Binary search loop tracking min abs difference to targeteasy
4. 20.Inorder Successor in BST
   If right subtree exists: min of right subtree. Else: last left-turn ancestormedium
5. 21.Inorder Predecessor in BST
   If left subtree exists: max of left subtree. Else: last right-turn ancestormedium
6. 22.Unique Binary Search Trees
   Catalan number DP: G(n) = sum(G(i-1) * G(n-i))medium
7. 23.Unique Binary Search Trees II
   Divide & conquer generating all valid BST combinationsmedium
8. 24.Serialize and Deserialize BST
   Preorder traversal string (no nil markers needed if upper/lower bounds used)medium
9. 25.Split BST
   Recursive split returning [<= val subtree, > val subtree]medium

How to Think

1. Tree has ordering property?Binary Search Tree (BST)
2. Need search for value?val < node -> go Left, val > node -> go Right
3. Need sorted values from BST?Inorder Traversal (Left-Root-Right)
4. Need Kth smallest?Inorder + Count to K
5. Need validate BST?Lower Bound < Node < Upper Bound
6. Need LCA in BST?Order split point (both < node -> left, both > node -> right)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Iterative BST Search: O(H) time, O(1) space
func searchBST(root *TreeNode, target int) *TreeNode {
    for root != nil {
        if root.Val == target {
            return root
        }
        if target < root.Val {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return nil
}

// Lowest Common Ancestor in a BST using Ordering
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for root != nil {
        if p.Val < root.Val && q.Val < root.Val {
            root = root.Left
        } else if p.Val > root.Val && q.Val > root.Val {
            root = root.Right
        } else {
            return root // Split point is the LCA!
        }
    }
    return nil
}

The Golden Rule: BST + Inorder = Sorted Array

// Find Kth Smallest Element in a BST
func kthSmallest(root *TreeNode, k int) int {
    count := 0
    result := 0

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil || count >= k {
            return
        }

        inorder(node.Left)

        count++
        if count == k {
            result = node.Val
            return
        }

        inorder(node.Right)
    }

    inorder(root)
    return result
}

Delete Node in a BST (3 Cases)

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }

    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {
        // Found node to delete!
        if root.Left == nil {
            return root.Right
        }
        if root.Right == nil {
            return root.Left
        }

        // 2 Children case: find Inorder Successor (min in Right subtree)
        curr := root.Right
        for curr.Left != nil {
            curr = curr.Left
        }
        root.Val = curr.Val
        root.Right = deleteNode(root.Right, curr.Val)
    }
    return root
}

Smaller -> Go Left  |  Larger -> Go Right
BST + Inorder = Strictly Sorted Array
Validate BST = Lower Bound < Node.Val < Upper Bound
LCA in BST = First node where targets p and q split
Delete Node (2 Children) -> Replace with Inorder Successor (Min of Right Subtree)

Common Interview Mistakes

Interview Rules

1. 1. Ordered binary tree? → BST
2. 2. Smaller target? → Go Left (target < node.Val)
3. 3. Larger target? → Go Right (target > node.Val)
4. 4. Sorted elements needed? → Inorder Traversal (Left - Root - Right)
5. 5. Validate BST? → Pass lower < node.Val < upper bounds downward
6. 6. LCA in BST? → First split point node where p and q diverge
7. 7. Delete node with 2 children? → Replace with Inorder Successor (minimum of right subtree)
8. 8. Overall Complexity → Search/Insert/Delete: O(H) (O(log N) balanced, O(N) skewed)

BST
Left            → Smaller
Right           → Larger
Search          → Choose one side
Inorder         → Sorted array
Validate        → Lower < Node < Upper
Kth Smallest    → Inorder + Count
LCA             → Find split point
Delete 2 Ch.    → Successor / Predecessor
Balanced        → O(log N)
Skewed          → O(N)

💡 Golden Rule: "Use the BST ordering to eliminate the part of the tree that cannot contain your answer."