Topic 57 of 79

BST

Q: How do you validate if a Binary Tree is a valid Binary Search Tree?

You use a recursive function that takes the node, a minimum valid value, and a maximum valid value. For the root, min is -Infinity and max is +Infinity. As you traverse left, you update the max limit to the current node's value. As you traverse right, you update the min limit. If any node violates its bounds, return false.

Q: What is an AVL Tree or a Red-Black Tree?

They are 'Self-Balancing Binary Search Trees'. When nodes are inserted or deleted, these trees perform complex 'rotations' to ensure the tree never becomes degenerate (unbalanced). Java's `TreeMap` and `TreeSet` are internally implemented using Red-Black Trees to guarantee strict O(log N) performance.

Overview

A standard Binary Tree doesn't enforce any order, making search operations O(N). A Binary Search Tree (BST) imposes a strict mathematical rule on how nodes are arranged: 1. Every value in the left subtree must be less than the node's value. 2. Every value in the right subtree must be greater than the node's value.

This simple rule unlocks incredible performance. When searching for a value, you compare it to the root. If it's smaller, you completely eliminate the entire right half of the tree. If it's larger, you eliminate the left half. This halving process is identical to Binary Search in an array, resulting in O(log N) time complexity for Search, Insertion, and Deletion.

However, this O(log N) performance is only guaranteed if the tree is balanced. If you insert sorted data (e.g., 1, 2, 3, 4, 5) into a naive BST, it will form a straight line, degrading into a Linked List with O(N) performance.

Syntax

BST Insertion and Search

java

public class BST {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    TreeNode root;
    
    // O(log N) Insertion
    public void insert(int val) {
        root = insertRec(root, val);
    }
    
    private TreeNode insertRec(TreeNode root, int val) {
        // Base case: Found the empty spot!
        if (root == null) return new TreeNode(val);
        
        // Recursive routing based on BST rules
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        // If equal, do nothing (no duplicates allowed in this BST)
        return root;
    }
    
    // O(log N) Search
    public boolean search(int val) {
        TreeNode current = root;
        while (current != null) {
            if (current.val == val) return true; // Found it!
            
            // Choose the path
            if (val < current.val) current = current.left;
            else current = current.right;
        }
        return false; // Reached a leaf without finding it
    }
}

Common Pitfalls

Assuming a naive BST is always O(log N). In an interview, if you claim a BST search is O(log N), the interviewer will ask 'Always?'. The correct answer is: 'Only if it is balanced. The worst-case is O(N) if the tree becomes a degenerate linked list.'
Violating the BST property during complex modifications. Deleting a node with two children is notoriously tricky. You must find the 'Inorder Successor' (the smallest node in the right subtree), swap its value with the target node, and then delete the successor. If done incorrectly, the BST rules are permanently broken.
Checking only immediate children for BST validity. To validate if a tree is a BST, it's not enough to check left < root < right. A node deep in the left subtree might accidentally be larger than the absolute root. You must enforce MIN and MAX boundaries during traversal.

Interview Questions

How do you validate if a Binary Tree is a valid Binary Search Tree?

You use a recursive function that takes the node, a minimum valid value, and a maximum valid value. For the root, min is -Infinity and max is +Infinity. As you traverse left, you update the max limit to the current node's value. As you traverse right, you update the min limit. If any node violates its bounds, return false.

What is an AVL Tree or a Red-Black Tree?

They are 'Self-Balancing Binary Search Trees'. When nodes are inserted or deleted, these trees perform complex 'rotations' to ensure the tree never becomes degenerate (unbalanced). Java's TreeMap and TreeSet are internally implemented using Red-Black Trees to guarantee strict O(log N) performance.

Real-World Example

Database Indexing relies heavily on balanced search trees (usually B-Trees, a generalized form of BSTs). When you query a massive database (SELECT * WHERE id = 500), the database does not scan all 10 million rows. It traverses a B-Tree index, finding the exact disk location of ID 500 in a few milliseconds.

example

java

// Java's built-in self-balancing BST
import java.util.TreeMap;

public class DatabaseIndex {
    public static void main(String[] args) {
        // TreeMap guarantees O(log N) operations and keeps keys sorted
        TreeMap<Integer, String> index = new TreeMap<>();
        
        index.put(500, "Disk_Sector_A12");
        index.put(100, "Disk_Sector_B04");
        index.put(900, "Disk_Sector_Z99");
        
        // Finding an item is blazing fast, even with millions of keys
        String diskLocation = index.get(500); 
    }
}

Check Your Knowledge

Test your understanding of BST with these quick questions.

What rule must every node in a Binary Search Tree obey?

What happens if you insert already sorted data (1, 2, 3, 4, 5) into a standard, non-balancing BST?

Which Java collection uses a Red-Black Tree (a balanced BST) internally?

Take Java Quiz

Overview

Syntax

BST Insertion and Search

java

public class BST {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    TreeNode root;
    
    // O(log N) Insertion
    public void insert(int val) {
        root = insertRec(root, val);
    }
    
    private TreeNode insertRec(TreeNode root, int val) {
        // Base case: Found the empty spot!
        if (root == null) return new TreeNode(val);
        
        // Recursive routing based on BST rules
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        // If equal, do nothing (no duplicates allowed in this BST)
        return root;
    }
    
    // O(log N) Search
    public boolean search(int val) {
        TreeNode current = root;
        while (current != null) {
            if (current.val == val) return true; // Found it!
            
            // Choose the path
            if (val < current.val) current = current.left;
            else current = current.right;
        }
        return false; // Reached a leaf without finding it
    }
}

Common Pitfalls

Assuming a naive BST is always O(log N). In an interview, if you claim a BST search is O(log N), the interviewer will ask 'Always?'. The correct answer is: 'Only if it is balanced. The worst-case is O(N) if the tree becomes a degenerate linked list.'
Violating the BST property during complex modifications. Deleting a node with two children is notoriously tricky. You must find the 'Inorder Successor' (the smallest node in the right subtree), swap its value with the target node, and then delete the successor. If done incorrectly, the BST rules are permanently broken.
Checking only immediate children for BST validity. To validate if a tree is a BST, it's not enough to check left < root < right. A node deep in the left subtree might accidentally be larger than the absolute root. You must enforce MIN and MAX boundaries during traversal.

Interview Questions

How do you validate if a Binary Tree is a valid Binary Search Tree?

What is an AVL Tree or a Red-Black Tree?

Real-World Example

example

java

// Java's built-in self-balancing BST
import java.util.TreeMap;

public class DatabaseIndex {
    public static void main(String[] args) {
        // TreeMap guarantees O(log N) operations and keeps keys sorted
        TreeMap<Integer, String> index = new TreeMap<>();
        
        index.put(500, "Disk_Sector_A12");
        index.put(100, "Disk_Sector_B04");
        index.put(900, "Disk_Sector_Z99");
        
        // Finding an item is blazing fast, even with millions of keys
        String diskLocation = index.get(500); 
    }
}

Check Your Knowledge

Test your understanding of BST with these quick questions.