Binary Search Tree

A Binary Search Tree (BST) is a type of binary tree where each node has at most two children, and the tree maintains a specific order. For any given node:

• The left subtree contains only nodes with values less than the node’s value.
• The right subtree contains only nodes with values greater than the node’s value.

This property enables efficient searching, insertion, and deletion operations, making BSTs useful for various applications where ordered data needs to be stored and accessed quickly.

Basic Operations on a BST and Their Complexity Analysis

1. Insertion

// class TreeNode {
//     int val;
//     TreeNode left, right;

//     public TreeNode(int val) {
//         this.val = val;
//         left = right = null;
//     }
// }

public class BSTOperations {
    // Insert a value into the BST
    public TreeNode insert(TreeNode root, int key) {
        if (root == null) {
            return new TreeNode(key);
        }
        if (key < root.val) {
            root.left = insert(root.left, key);
        } else if (key > root.val) {
            root.right = insert(root.right, key);
        }
        return root;
    }
}

Time Complexity

1. Insertion Process:

   • Traversal: The traversal path depends on the value of the key being inserted. The function will travel down one branch of the tree, either to the left or right, at each recursive step.
   • Number of Recursive Calls:
     • In a balanced BST, the height h of the tree is approximately , where n is the number of nodes. Therefore, the function will make up to recursive calls.
     • In an unbalanced BST (e.g., if the tree resembles a linked list), the height h can be as large as n. In this case, the function may make up to recursive calls.

Overall Time Complexity:

• Average Case: for a balanced BST.
• Worst Case: for an unbalanced BST (e.g., skewed tree).

Space Complexity

1. Call Stack (Recursive Space):

   • The space complexity due to recursion is directly proportional to the maximum depth of the call stack.
   • In a balanced BST, the maximum depth of the recursive stack is .
   • In an unbalanced BST, the maximum depth can reach if the tree is skewed.

2. Auxiliary Space:

   • The function itself does not use additional space apart from the recursion stack.

Overall Space Complexity:

• Average Case: for a balanced BST.
• Worst Case: for an unbalanced BST.

2. Search

public boolean search(TreeNode root, int key) {
    if (root == null) return false;
    if (root.val == key) return true;
    if (key < root.val) {
        return search(root.left, key);
    } else {
        return search(root.right, key);
    }
}

Time Complexity

1. Search Process:
   • Traversal: At each recursive step, the function decides to move left (search(root.left, key)) or right (search(root.right, key)) based on the value of key relative to root.val.
   • Number of Recursive Calls:
     • In a balanced BST, the height h of the tree is approximately , where n is the number of nodes. The function will make up to recursive calls in this case.
     • In an unbalanced BST (e.g., if the tree is skewed), the height h can be up to n. The function may make up to recursive calls.

Overall Time Complexity:

• Average Case: for a balanced BST.
• Worst Case: for an unbalanced BST.

Space Complexity

1. Call Stack (Recursive Space):

   • The space complexity due to recursion is directly proportional to the maximum depth of the call stack.
   • In a balanced BST, the maximum depth of the recursive stack is .
   • In an unbalanced BST, the maximum depth can reach if the tree is skewed.

2. Auxiliary Space:

   • The function itself does not use any additional space beyond the call stack.

Overall Space Complexity:

• Average Case: for a balanced BST.
• Worst Case: for an unbalanced BST.

3. Deletion

public TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        // Node with only one child or no child
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Node with two children: get the inorder successor (smallest in the right subtree)
        root.val = findMin(root.right);
        root.right = delete(root.right, root.val);
    }
    return root;
}

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

Time Complexity

1. Traversal and Search for the Node:

   • Number of Recursive Calls:
     • In a balanced BST, the traversal depth is , where n is the number of nodes in the tree.
     • In an unbalanced BST, the traversal depth can be up to if the tree is skewed.

2. Deleting the Node:

   • Case 1: Node with No Children:
     • Directly removes the node by returning null.
     • Time Complexity: .
   • Case 2: Node with One Child:
     • The node is replaced by its single child.
     • Time Complexity: .
   • Case 3: Node with Two Children:
     • Finds the in-order successor (the smallest node in the right subtree) using the findMin method, and recursively deletes it.
     • Finding the In-order Successor: The findMin method traverses the leftmost path in the right subtree.
       • Time Complexity of findMin: , where h is the height of the tree.

Overall Time Complexity:

• Average Case: for a balanced BST.
• Worst Case: for an unbalanced BST, including finding and deleting the node.

Space Complexity

1. Call Stack (Recursive Space):

   • The space complexity depends on the recursion depth, which is proportional to the height of the tree.
   • Balanced Tree: space for the recursive stack.
   • Unbalanced Tree: space for the recursive stack in the worst case.

2. Auxiliary Space:

   • The findMin method does not use any additional space other than traversing nodes.

Overall Space Complexity:

• Average Case: for balanced trees.
• Worst Case: for unbalanced trees.

I just read a lesson on **Binary Search Tree** (DSA) and want to truly understand it. Explain Binary Search Tree from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Binary Search Tree** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Binary Search Tree** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Binary Search Tree** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.