🌳 Binary Search Trees Fundamentals

🎯 What is a Binary Search Tree?

A Binary Search Tree (BST) is a node-based binary tree data structure where each node has at most two children (left and right). The BST property: for any node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

Average: O(log n) | Worst-case: O(n) | Space: O(n)

The BST Property

Core Insight: The BST property enables efficient searching — at each node, you can decide to go left or right, eliminating half of the remaining tree. This is the tree analog of binary search on a sorted array.

Analogy: Like a phone book organized by name. To find "Miller", you open the middle, determine if "Miller" is before or after, and repeat — eliminating half the book each time.

📌 Ordered Structure📌 Left < Root < Right📌 Recursive Definition📌 No Duplicates (typically)

# Basic BST Node Structure
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# BST Property Example:
#        8
#      /   \
#     3     10
#    / \      \
#   1   6      14
#      / \    /
#     4   7  13
# This is a valid BST because for every node:
# left subtree values < node value < right subtree values

        8
      /   \
     3     10
    / \      \
   1   6      14
      / \    /
     4   7  13

📐 BST Properties & Invariants

🎯 Key BST Invariants

Binary Tree: Each node has ≤ 2 children
Ordering Property: left subtree values < node value < right subtree values
No Duplicates: Standard BSTs don't allow duplicate keys (can be modified to allow with extra rules)
Inorder Traversal: Always yields nodes in sorted order
Recursive Structure: Every subtree is itself a BST

# Inorder traversal of BST gives sorted order
def inorder_traversal(root):
    result = []
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    inorder(root)
    return result

# Example: BST [5,3,7,1,4,6,8] inorder = [1,3,4,5,6,7,8]

⚡ Core Operations (Search/Insert/Delete)

🎯 Search, Insert, Delete

Search: Compare target with node value, go left or right accordingly
Insert: Traverse like search, insert at the first null position found
Delete: Three cases: leaf node, node with one child, node with two children (find successor)

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(self.root, val)
    
    def _insert(self, node, val):
        if val < node.val:
            if node.left:
                self._insert(node.left, val)
            else:
                node.left = TreeNode(val)
        elif val > node.val:
            if node.right:
                self._insert(node.right, val)
            else:
                node.right = TreeNode(val)
    
    def search(self, val):
        return self._search(self.root, val)
    
    def _search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)
    
    def delete(self, val):
        self.root = self._delete(self.root, val)
    
    def _delete(self, node, val):
        if not node:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # Case 1: No children
            if not node.left and not node.right:
                return None
            # Case 2: One child
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            # Case 3: Two children
            successor = self._min(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
        return node
    
    def _min(self, node):
        while node.left:
            node = node.left
        return node

🔄 Tree Traversals (DFS & BFS)

🎯 Visiting All Nodes

Inorder (Left-Root-Right): Returns sorted order
Preorder (Root-Left-Right): Useful for tree copying/serialization
Postorder (Left-Right-Root): Useful for tree deletion
Level Order (BFS): Visits nodes by level

from collections import deque

def inorder(node, result):
    if node:
        inorder(node.left, result)
        result.append(node.val)
        inorder(node.right, result)

def preorder(node, result):
    if node:
        result.append(node.val)
        preorder(node.left, result)
        preorder(node.right, result)

def postorder(node, result):
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.val)

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

⏱️ Time & Space Complexities

🎯 Performance Analysis

Average Case (balanced tree): O(log n) for search, insert, delete
Worst Case (skewed tree): O(n) for all operations (like a linked list)
Space Complexity: O(n) for storing nodes, O(h) recursion stack for traversals
Height of balanced tree: h ≈ log₂(n)
Height of skewed tree: h = n

Why Balanced BSTs Matter

Standard BST performance depends on tree height. Balanced trees (AVL, Red-Black) guarantee O(log n) height, ensuring optimal performance even for worst-case insertion orders.

💻 Multiple Implementations

# 1. Iterative Search (no recursion)
def search_iterative(root, val):
    curr = root
    while curr:
        if curr.val == val:
            return curr
        elif val < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    return None

# 2. Insert using iteration
def insert_iterative(root, val):
    if not root:
        return TreeNode(val)
    curr = root
    while True:
        if val < curr.val:
            if curr.left:
                curr = curr.left
            else:
                curr.left = TreeNode(val)
                break
        else:
            if curr.right:
                curr = curr.right
            else:
                curr.right = TreeNode(val)
                break
    return root

# 3. Class-based with __slots__ for memory efficiency
class Node:
    __slots__ = ('val', 'left', 'right')
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

⚖️ Balanced BSTs (AVL, Red-Black)

🎯 Self-Balancing Trees

Balanced BSTs automatically maintain a height of O(log n), guaranteeing optimal performance even for worst-case insertion sequences.

AVL Tree: Strictly balanced (height difference ≤ 1). Faster lookups, slower inserts.
Red-Black Tree: Relaxed balance (approximate). Faster inserts, used in Java TreeMap, C++ map.
Splay Tree: Self-adjusting, recently accessed nodes move to root.
B-Trees: Used in databases and file systems.

🎯 Successor & Predecessor

🎯 Finding Next/Previous in Order

Inorder Successor: The next larger value in the BST. Inorder Predecessor: The next smaller value.

def inorder_successor(root, target):
    """Find the next larger value after target"""
    successor = None
    curr = root
    while curr:
        if target.val < curr.val:
            successor = curr
            curr = curr.left
        elif target.val > curr.val:
            curr = curr.right
        else:
            # Target found, go to right subtree then leftmost
            if curr.right:
                successor = curr.right
                while successor.left:
                    successor = successor.left
            break
    return successor

def inorder_predecessor(root, target):
    """Find the next smaller value before target"""
    predecessor = None
    curr = root
    while curr:
        if target.val > curr.val:
            predecessor = curr
            curr = curr.right
        elif target.val < curr.val:
            curr = curr.left
        else:
            if curr.left:
                predecessor = curr.left
                while predecessor.right:
                    predecessor = predecessor.right
            break
    return predecessor

✅ BST Validation & Properties

🎯 Check if a Binary Tree is a BST

def is_valid_bst(root):
    """Check if tree satisfies BST property"""
    def validate(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    return validate(root, float('-inf'), float('inf'))

# Alternative: Inorder traversal should be sorted
def is_bst_inorder(root):
    result = []
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    inorder(root)
    return all(result[i] < result[i+1] for i in range(len(result)-1))

👥 Lowest Common Ancestor

🎯 Finding Shared Ancestor in BST

def lowest_common_ancestor(root, p, q):
    """Find LCA in BST - O(h) time"""
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

# For general binary tree (non-BST)
def lca_binary_tree(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca_binary_tree(root.left, p, q)
    right = lca_binary_tree(root.right, p, q)
    if left and right:
        return root
    return left if left else right

🔢 Kth Smallest/Largest

🎯 Finding Order Statistics

def kth_smallest(root, k):
    """Find kth smallest element using inorder traversal"""
    def inorder(node):
        if not node:
            return
        yield from inorder(node.left)
        yield node.val
        yield from inorder(node.right)
    
    for i, val in enumerate(inorder(root), 1):
        if i == k:
            return val
    return None

# Optimized O(h + k) solution with count
def kth_smallest_optimized(root, k):
    count = 0
    result = None
    def inorder(node):
        nonlocal count, result
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)
    inorder(root)
    return result

📊 Range Queries & Interval Trees

🎯 Finding Values in a Range

def range_query(root, low, high, result=None):
    """Return all values between low and high"""
    if result is None:
        result = []
    if not root:
        return result
    if low < root.val:
        range_query(root.left, low, high, result)
    if low <= root.val <= high:
        result.append(root.val)
    if high > root.val:
        range_query(root.right, low, high, result)
    return result

def count_in_range(root, low, high):
    """Count nodes with values in [low, high]"""
    if not root:
        return 0
    if root.val < low:
        return count_in_range(root.right, low, high)
    if root.val > high:
        return count_in_range(root.left, low, high)
    return 1 + count_in_range(root.left, low, high) + count_in_range(root.right, low, high)

🌍 Real-World Applications

Database Indexing: B-Trees (generalization of BST) for efficient lookups
File Systems: Directory structures, file organization
Compilers: Abstract Syntax Trees (ASTs)
Routing Algorithms: Network routing tables
Auto-complete: Tries + BST for prefix matching
Priority Queues: Binary heaps (complete BST based)
Ordered Dictionaries: Java TreeMap, C++ std::map

💪 Practice & Interview Patterns

🎯 Classic BST Problems

Validate BST: Check if tree satisfies BST property
Lowest Common Ancestor: Find shared ancestor of two nodes
Inorder Successor: Find next node in BST
Insert/Delete: Core operations
Convert Sorted Array to BST: Build balanced BST
Two Sum in BST: Find two nodes summing to target
Range Sum Query: Sum of values in range
Recover BST: Fix two swapped nodes

# Sorted Array to Balanced BST
def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid+1:])
    return root

# Two Sum in BST
def find_target(root, k):
    seen = set()
    def dfs(node):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)