Trees

Binary Search Tree

TimeO(log n) SpaceO(n)

Think of a dictionary. To find a word, you open to the middle. If your word comes earlier alphabetically, you look left; if later, you look right. A BST works the same way — every node is a decision point that sends you left or right.

When to use it: You need fast insert, delete, and lookup in a dynamic dataset. Also when inorder traversal giving sorted order is useful (e.g., finding the k-th smallest element).

Key insight: The BST property (left < root < right) means inorder traversal produces sorted output. This also means search, insert, and delete all follow a root-to-leaf path, taking O(h) time.

Common trap: Assuming O(log n) performance. An unbalanced BST (e.g., inserting sorted data) degrades to a linked list with O(n) operations. Use self-balancing trees (AVL, Red-Black) for guarantees.

function search(node, target):
    if node == null:
        return null
    if target == node.val:
        return node
    if target < node.val:
        return search(node.left, target)
    else:
        return search(node.right, target)

function insert(node, val):
    if node == null:
        return new Node(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

function delete(node, val):
    if node == null:
        return null
    if val < node.val:
        node.left = delete(node.left, val)
    else if val > node.val:
        node.right = delete(node.right, val)
    else:
        # Found the node to delete
        if node.left == null:
            return node.right       # replace with right child
        if node.right == null:
            return node.left        # replace with left child
        # Two children: replace with inorder successor
        successor = findMin(node.right)
        node.val = successor.val
        node.right = delete(node.right, successor.val)
    return node

function findMin(node):
    while node.left != null:
        node = node.left
    return node

class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def search_bst(root: TreeNode | None, target: int) -> TreeNode | None:
    if not root or root.val == target:
        return root
    if target < root.val:
        return search_bst(root.left, target)
    return search_bst(root.right, target)


def insert_bst(root: TreeNode | None, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root


def delete_bst(root: TreeNode | None, val: int) -> TreeNode | None:
    if not root:
        return None
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Find inorder successor (smallest in right subtree)
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)
    return root


def kth_smallest(root: TreeNode, k: int) -> int:
    """Find the k-th smallest element using inorder traversal."""
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        current = current.right

    return -1


def is_valid_bst(root: TreeNode | None,
                 lo: float = float("-inf"),
                 hi: float = float("inf")) -> bool:
    if not root:
        return True
    if root.val <= lo or root.val >= hi:
        return False
    return (is_valid_bst(root.left, lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

Problem: Given the root of a binary tree, determine if it is a valid binary search tree.

How would you approach this?

Answer: This is a BST validation problem. Pass down valid range bounds: each node must be within (lo, hi). The left child narrows the upper bound; the right child narrows the lower bound. Alternatively, inorder traversal of a valid BST produces a strictly increasing sequence.

Problem: Given a BST and an integer k, find the k-th smallest element.

How would you approach this?

Answer: This exploits the BST inorder property. Inorder traversal visits nodes in ascending order. Perform an iterative inorder traversal and return the k-th node visited. Time: O(h + k).

Time: O(log n) average for search, insert, and delete — each follows a root-to-leaf path of height h. For a balanced BST, h = O(log n). Worst case: O(n) if the tree is completely skewed (like a linked list).

Space: O(n) to store the tree itself. Individual operations use O(h) space for recursion — O(log n) balanced, O(n) worst case. Iterative versions reduce operation space to O(1) for search.