Advanced BST: Validation and Restoration

Validate Binary Search Tree (LeetCode 98)

A common mistake is only checking immediate children. The correct approach is to enforce a range $(min, max)$ for every node:

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

private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    
    // Left child must be in (min, currentVal)
    // Right child must be in (currentVal, max)
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

Iterative Approach (In-order Verification): Since in-order traversal of a BST must be strictly increasing, we track the previous node's value.

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    long previous = Long.MIN_VALUE;
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        if (current.val <= previous) return false;
        previous = current.val;
        current = current.right;
    }
    return true;
}

BST Iterator (LeetCode 173)

Implement next() and hasNext() with amortized O(1) time and O(h) space using an explicit stack to simulate in-order traversal:

class BSTIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) {
        pushLeftChains(root);
    }

    public int next() {
        TreeNode node = stack.pop();
        // If the node has a right child, we need to push its left branch to continue in-order
        pushLeftChains(node.right);
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    private void pushLeftChains(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

Recover Binary Search Tree (LeetCode 99)

Two nodes were accidentally swapped. Find and fix them. While O(n) space is easy, O(1) space requires Morris Traversal.

public void recoverTree(TreeNode root) {
    TreeNode first = null, second = null, previous = null;
    TreeNode current = root, predecessor;
    
    while (current != null) {
        if (current.left == null) {
            // Process node
            if (previous != null && previous.val > current.val) {
                if (first == null) first = previous;
                second = current;
            }
            previous = current;
            current = current.right;
        } else {
            predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null; // Corrected tree structure
                // Process node
                if (previous != null && previous.val > current.val) {
                    if (first == null) first = previous;
                    second = current;
                }
                previous = current;
                current = current.right;
            }
        }
    }
    // Perform the swap to restore BST order
    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}

K-th Smallest Element in a BST (LeetCode 230)

In-order traversal visits nodes in ascending order. The $k$-th visited node is the answer.

private int visitCount = 0;
private int result = 0;

public int kthSmallest(TreeNode root, int k) {
    inorderTraverse(root, k);
    return result;
}

private void inorderTraverse(TreeNode node, int k) {
    if (node == null || visitCount >= k) return;
    
    inorderTraverse(node.left, k);
    
    if (++visitCount == k) {
        result = node.val;
        return;
    }
    
    inorderTraverse(node.right, k);
}

Summary