Binary Search Trees

TreeNode search(TreeNode root, int target) {
    // Base case: empty tree or found the target
    if (root == null || root.val == target) {
        return root;
    }
    
    // Decide direction based on BST property
    if (target < root.val) {
        return search(root.left, target);   // Go left
    } else {
        return search(root.right, target);  // Go right
    }
}

The recursive approach is the most intuitive way to search a BST. Think of it like giving directions: "If you're looking for a smaller number, go left. If you're looking for a larger number, go right. Keep following these directions until you find what you're looking for or reach a dead end." The function calls itself with a smaller subtree each time, naturally eliminating half of the remaining nodes with every recursive call. This elegant solution directly mirrors how we think about the problem!

TreeNode searchIterative(TreeNode root, int target) {
    // Keep going until we find target or hit null
    while (root != null && root.val != target) {
        if (target < root.val) {
            root = root.left;   // Move left
        } else {
            root = root.right;  // Move right
        }
    }
    return root;  // Either found node or null
}

The iterative approach does exactly the same thing as recursion, but uses a while loop instead of function calls. Why would you prefer this? Space efficiency! Recursive calls build up on the call stack - in a very deep tree (like one with 10,000 levels), you could get a stack overflow. The iterative version uses constant O(1) space regardless of tree depth. Interviewers often ask candidates to convert recursive solutions to iterative - this is a perfect example of that skill!

TreeNode findMin(TreeNode root) {
    while (root.left != null) {
        root = root.left;
    }
    return root;
}

TreeNode findMax(TreeNode root) {
    while (root.right != null) {
        root = root.right;
    }
    return root;
}

Finding the minimum and maximum values in a BST is beautifully simple thanks to the BST property! Remember: in a BST, all smaller values are to the left and all larger values are to the right. So where's the smallest value? At the leftmost node - just keep going left until you can't anymore! Where's the largest? At the rightmost node. No comparisons needed, no checking values - just follow the path. These helper functions are used heavily in BST deletion (to find the inorder successor) and in many interview problems!

TreeNode insert(TreeNode root, int val) {
    // Base case: found the spot - create new node
    if (root == null) {
        return new TreeNode(val);
    }
    
    // Decide direction based on BST property
    if (val < root.val) {
        root.left = insert(root.left, val);    // Go left
    } else if (val > root.val) {
        root.right = insert(root.right, val);  // Go right
    }
    // If equal, ignore duplicates (standard BST behavior)
    
    return root;  // Return unchanged root to maintain tree structure
}

The recursive insert is elegant and intuitive. It follows the same path as search: compare, go left or right, repeat. The magic is in the base case - when we hit null, we've found where the new value belongs! We create a new node and return it. The parent's assignment (root.left = insert(...)) connects the new node to the tree. Always return root at the end - this is what makes the recursion work correctly!

TreeNode insertIterative(TreeNode root, int val) {
    TreeNode newNode = new TreeNode(val);
    
    // Special case: empty tree
    if (root == null) {
        return newNode;
    }
    
    TreeNode curr = root;
    TreeNode parent = null;
    
    // Find the correct position
    while (curr != null) {
        parent = curr;  // Track parent before moving
        if (val < curr.val) {
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
    
    // Attach new node to parent
    if (val < parent.val) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    
    return root;
}

The iterative approach requires more code but uses O(1) space - no recursion stack! The key difference: we need to manually track the parent pointer because once curr becomes null, we lose access to where we were. The loop finds the correct spot, then we make one final comparison with the parent to decide if the new node goes left or right. This is a common interview follow-up: "Can you do it without recursion?"

TreeNode buildBST(int[] nums) {
    TreeNode root = null;
    for (int num : nums) {
        root = insert(root, num);  // Insert each element
    }
    return root;
}

This utility function builds a complete BST from an array by inserting elements one at a time. Critical insight: the array's order determines the tree's shape! Insert [4,2,6,1,3,5,7] and you get a balanced tree. Insert [1,2,3,4,5,6,7] (sorted) and you get a "linked list" - each node only has a right child. For interviews, remember: if you need a balanced BST from sorted data, use the "build from sorted array" technique (divide and conquer) instead!

TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    
    // Search for node to delete
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        // Found the node to delete - handle 3 cases
        
        // Case 1: Leaf node (no children)
        if (root.left == null && root.right == null) {
            return null;
        }
        
        // Case 2: One child only
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Case 3: Two children - use inorder successor
        TreeNode successor = findMin(root.right);
        root.val = successor.val;
        root.right = delete(root.right, successor.val);
    }
    
    return root;
}

The delete function first searches for the node (like regular BST search), then handles three cases based on children count. Case 3 is the tricky one: we find the inorder successor (smallest in right subtree), copy its value to the current node, then recursively delete the successor. This works because the successor has at most one child (no left child by definition), so deleting it falls into Case 1 or 2!

TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

This helper is essential for delete - it finds the inorder successor. In a BST, the smallest value in any subtree is always at the leftmost position. We use this to find the "next" value in sorted order when deleting a node with two children. The successor is guaranteed to have no left child (otherwise it wouldn't be the minimum)!

TreeNode deleteWithPredecessor(TreeNode root, int key) {
    if (root == null) return null;
    
    if (key < root.val) {
        root.left = deleteWithPredecessor(root.left, key);
    } else if (key > root.val) {
        root.right = deleteWithPredecessor(root.right, key);
    } else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Find inorder predecessor (largest in left subtree)
        TreeNode predecessor = findMax(root.left);
        root.val = predecessor.val;
        root.left = deleteWithPredecessor(root.left, predecessor.val);
    }
    
    return root;
}

Instead of the inorder successor, you can use the inorder predecessor (largest value in left subtree). The logic is symmetric: find the rightmost node in the left subtree, copy its value, then delete it. Interview tip: Mention this alternative to show deeper understanding. Both approaches maintain the BST property perfectly!

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    
    // Node must be within valid range
    if (node.val <= min || node.val >= max) {
        return false;
    }
    
    // Left subtree: max becomes current value
    // Right subtree: min becomes current value
    return validate(node.left, min, node.val) && 
           validate(node.right, node.val, max);
}

This is the most intuitive approach! Instead of just checking parent-child relationships, we pass down a valid range that tightens as we go deeper. When going left, the current node becomes the new upper bound. When going right, it becomes the new lower bound. We use Long to handle edge cases where node values are Integer.MIN_VALUE or Integer.MAX_VALUE.

boolean isValidBSTInorder(TreeNode root) {
    Stack stack = new Stack<>();
    TreeNode prev = null;
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        // Go all the way left
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        
        curr = stack.pop();
        
        // Check if current > previous (sorted order)
        if (prev != null && curr.val <= prev.val) {
            return false;
        }
        
        prev = curr;
        curr = curr.right;
    }
    
    return true;
}

This method exploits the fact that inorder traversal = sorted order for a valid BST. We do an iterative inorder traversal and check if each value is greater than the previous. The moment we find curr.val <= prev.val, we know it's invalid. This approach is elegant and shows understanding of BST properties!

TreeNode prev = null;  // Instance variable

boolean isValidBSTRecursive(TreeNode root) {
    if (root == null) return true;
    
    // Check left subtree first
    if (!isValidBSTRecursive(root.left)) return false;
    
    // Check current node against previous
    if (prev != null && root.val <= prev.val) return false;
    prev = root;
    
    // Check right subtree
    return isValidBSTRecursive(root.right);
}

Same logic as Method 2, but recursive and cleaner. The instance variable prev tracks the last node visited in inorder sequence. We visit left subtree, check current node, then visit right subtree - classic inorder pattern. Some consider this less elegant due to the instance variable, but the code is very readable!

int kthSmallest(TreeNode root, int k) {
    Stack stack = new Stack<>();
    TreeNode curr = root;
    int count = 0;
    
    while (curr != null || !stack.isEmpty()) {
        // Go all the way left first
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        
        // Pop and process
        curr = stack.pop();
        count++;
        
        // Found kth smallest!
        if (count == k) {
            return curr.val;
        }
        
        // Move to right subtree
        curr = curr.right;
    }
    
    return -1;  // k is larger than tree size
}

We use iterative inorder traversal which visits nodes in sorted order. Count each visited node, and when count reaches k, we've found our answer! The key optimization: we can exit early once we find the kth element - no need to traverse the entire tree. Time complexity is O(H + k) where H is height to reach the leftmost node, then k more steps.

int kthLargest(TreeNode root, int k) {
    Stack stack = new Stack<>();
    TreeNode curr = root;
    int count = 0;
    
    while (curr != null || !stack.isEmpty()) {
        // Go all the way RIGHT first (reverse!)
        while (curr != null) {
            stack.push(curr);
            curr = curr.right;
        }
        
        curr = stack.pop();
        count++;
        
        if (count == k) {
            return curr.val;
        }
        
        // Move to LEFT subtree (reverse!)
        curr = curr.left;
    }
    
    return -1;
}

For kth largest, we simply reverse the inorder traversal: go right first, then left. This gives us values in descending order. The 1st value visited is the largest, 2nd is second-largest, etc. Same logic, just swap left and right! This is more efficient than finding (n-k+1)th smallest because we don't need to know n.

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            // Both nodes in left subtree
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            // Both nodes in right subtree
            root = root.right;
        } else {
            // Split point found - this is the LCA!
            return root;
        }
    }
    return null;
}

The BST property makes LCA incredibly efficient! We don't need to explore both subtrees like in a regular binary tree. If both p and q are smaller than root, their LCA must be in the left subtree. If both are larger, it's in the right subtree. The moment they "split" (one goes left, one goes right, or one equals root), we've found the LCA!

TreeNode lcaRecursive(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) {
        return lcaRecursive(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lcaRecursive(root.right, p, q);
    } else {
        return root;  // Split point = LCA
    }
}

The recursive version is shorter and cleaner - just 3 cases with direct recursion. Note how we don't need explicit null checks because we're guaranteed to find the LCA before hitting null (assuming p and q exist in the tree). Interview tip: Start with recursive for clarity, then offer to convert to iterative if space is a concern!

TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode successor = null;
    
    while (root != null) {
        if (p.val < root.val) {
            // Root could be successor, save it
            successor = root;
            root = root.left;
        } else {
            // Successor must be in right subtree
            root = root.right;
        }
    }
    
    return successor;
}

The inorder successor is the smallest value greater than p. We search the BST: when we go left, the current node is a potential successor (it's larger than p), so we save it. When we go right, the current node is too small. The last saved value when we exit is the smallest node that's still greater than p - exactly what we need!

TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
    TreeNode predecessor = null;
    
    while (root != null) {
        if (p.val > root.val) {
            // Root could be predecessor, save it
            predecessor = root;
            root = root.right;
        } else {
            // Predecessor must be in left subtree
            root = root.left;
        }
    }
    
    return predecessor;
}

The inorder predecessor is the largest value smaller than p - exactly the opposite of successor! When we go right, the current node is smaller than p, so it's a potential predecessor (save it). When we go left, we're looking for larger values that are still smaller than p. The last saved value is the largest node that's still smaller than p. Notice the symmetry: swap left↔right and <↔> from successor!

TreeNode sortedArrayToBST(int[] nums) {
    return buildBST(nums, 0, nums.length - 1);
}

TreeNode buildBST(int[] nums, int left, int right) {
    // Base case: no elements in range
    if (left > right) return null;
    
    // Pick middle element as root (ensures balance!)
    int mid = left + (right - left) / 2;
    
    // Create node and build subtrees recursively
    TreeNode node = new TreeNode(nums[mid]);
    node.left = buildBST(nums, left, mid - 1);    // Left half
    node.right = buildBST(nums, mid + 1, right);  // Right half
    
    return node;
}

This is a beautiful divide-and-conquer algorithm! Since the array is sorted, the middle element is perfect as root: everything before it goes in the left subtree, everything after goes in the right subtree. By always picking the middle, we guarantee both subtrees have roughly equal nodes, creating a height-balanced BST. The recursion naturally handles all levels of the tree!