Binary Search Tree Operations

Generated on 2025-07-10 02:03:41 Algorithm Cheatsheet for Technical Interviews

---

Binary Search Tree Operations Cheatsheet

1. Quick Overview

• What is it? A tree-based data structure where each node has at most two children (left and right), and for each node:
  • All nodes in the left subtree have values less than the node’s value.
  • All nodes in the right subtree have values greater than the node’s value.
• When to use it? Effective for:
  • Efficient searching, insertion, and deletion of elements.
  • Ordered data storage.
  • Implementing sorted sets and maps.
  • When frequent searching and sorting operations are required.

2. Time & Space Complexity

Operation	Average Case	Worst Case	Space Complexity
Search	O(log n)	O(n)	O(1)
Insert	O(log n)	O(n)	O(1)
Delete	O(log n)	O(n)	O(1)
Minimum	O(log n)	O(n)	O(1)
Maximum	O(log n)	O(n)	O(1)
Inorder Traversal	O(n)	O(n)	O(n)

• n: Number of nodes in the tree.
• Worst case occurs when the tree is skewed (essentially a linked list).

3. Implementation

Python

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, root, val):
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self._insert(root.left, val)
        else:
            root.right = self._insert(root.right, val)
        return root

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, root, val):
        if not root:
            return False
        if val == root.val:
            return True
        elif val < root.val:
            return self._search(root.left, val)
        else:
            return self._search(root.right, val)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, root, val):
        if not root:
            return root

        if val < root.val:
            root.left = self._delete(root.left, val)
        elif val > root.val:
            root.right = self._delete(root.right, val)
        else:
            # Node with only one child or no child
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left

            # Node with two children: Get the inorder successor
            root.val = self._minValueNode(root.right).val
            root.right = self._delete(root.right, root.val)

        return root

    def _minValueNode(self, node):
        current = node
        while(current.left is not None):
            current = current.left
        return current

    def inorder_traversal(self):
        result = []
        self._inorder_traversal(self.root, result)
        return result

    def _inorder_traversal(self, root, result):
        if root:
            self._inorder_traversal(root.left, result)
            result.append(root.val)
            self._inorder_traversal(root.right, result)

Java

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

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }

        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        return root;
    }

    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(TreeNode root, int val) {
        if (root == null) {
            return false;
        }

        if (val == root.val) {
            return true;
        } else if (val < root.val) {
            return searchRec(root.left, val);
        } else {
            return searchRec(root.right, val);
        }
    }

    public void delete(int val) {
        root = deleteRec(root, val);
    }

    private TreeNode deleteRec(TreeNode root, int val) {
        if (root == null) {
            return root;
        }

        if (val < root.val) {
            root.left = deleteRec(root.left, val);
        } else if (val > root.val) {
            root.right = deleteRec(root.right, val);
        } else {
            // node with only one child or no child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // node with two children: Get the inorder successor (smallest in the right subtree)
            root.val = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRec(root.right, root.val);
        }

        return root;
    }

    private int minValue(TreeNode root) {
        int minv = root.val;
        while (root.left != null) {
            minv = root.left.val;
            root = root.left;
        }
        return minv;
    }

    public void inorderTraversal() {
        inorderRec(root);
    }

    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.val + " ");
            inorderRec(root.right);
        }
    }
}

C++

#include <iostream>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class BinarySearchTree {
public:
    TreeNode *root;

    BinarySearchTree() {
        root = nullptr;
    }

    void insert(int val) {
        root = insertRec(root, val);
    }

    TreeNode* insertRec(TreeNode* root, int val) {
        if (root == nullptr) {
            root = new TreeNode(val);
            return root;
        }

        if (val < root->val) {
            root->left = insertRec(root->left, val);
        } else if (val > root->val) {
            root->right = insertRec(root->right, val);
        }
        return root;
    }

    bool search(int val) {
        return searchRec(root, val);
    }

    bool searchRec(TreeNode* root, int val) {
        if (root == nullptr) {
            return false;
        }

        if (val == root->val) {
            return true;
        } else if (val < root->val) {
            return searchRec(root->left, val);
        } else {
            return searchRec(root->right, val);
        }
    }

    void deleteNode(int val) {
        root = deleteRec(root, val);
    }

    TreeNode* deleteRec(TreeNode* root, int val) {
        if (root == nullptr) {
            return root;
        }

        if (val < root->val) {
            root->left = deleteRec(root->left, val);
        } else if (val > root->val) {
            root->right = deleteRec(root->right, val);
        } else {
            // node with only one child or no child
            if (root->left == nullptr) {
                TreeNode *temp = root->right;
                delete root;
                return temp;
            } else if (root->right == nullptr) {
                TreeNode *temp = root->left;
                delete root;
                return temp;
            }

            // node with two children: Get the inorder successor (smallest in the right subtree)
            root->val = minValue(root->right);

            // Delete the inorder successor
            root->right = deleteRec(root->right, root->val);
        }

        return root;
    }

    int minValue(TreeNode* root) {
        int minv = root->val;
        while (root->left != nullptr) {
            minv = root->left->val;
            root = root->left;
        }
        return minv;
    }

    void inorderTraversal() {
        inorderRec(root);
    }

    void inorderRec(TreeNode* root) {
        if (root != nullptr) {
            inorderRec(root->left);
            std::cout << root->val << " ";
            inorderRec(root->right);
        }
    }
};

4. Common Patterns

• Inorder Traversal: Visits nodes in ascending order (left, root, right). Used for printing sorted elements.
• Preorder Traversal: Visits nodes in the order (root, left, right). Useful for creating a copy of the tree.
• Postorder Traversal: Visits nodes in the order (left, right, root). Useful for deleting the tree, evaluating expressions.
• Finding Minimum/Maximum: Iterate to the leftmost/rightmost node.
• Finding Successor/Predecessor: The successor of a node is the next largest node in the tree. The predecessor is the next smallest.
• Balancing: Techniques like AVL trees, Red-Black trees ensure O(log n) performance in all cases.

5. Pro Tips

• Balancing is Key: Unbalanced trees lead to O(n) performance. Consider using self-balancing BSTs for dynamic data.
• Iterative vs. Recursive: Recursive implementations are often cleaner but can lead to stack overflow for very deep trees. Iterative implementations are generally more memory-efficient.
• Deletion Complexity: Deletion is the most complex operation. Carefully consider the different cases (node with no child, one child, two children). Using the inorder successor/predecessor is a common approach.
• Null Checks: Always handle null root/node cases in recursive functions to prevent errors.
• BST vs. Hash Table: BSTs maintain sorted order, which hash tables do not. BSTs are useful when ordering matters.

6. Practice Problems

1. Validate Binary Search Tree (LeetCode 98): Given a binary tree, determine if it is a valid binary search tree (BST).
2. Kth Smallest Element in a BST (LeetCode 230): Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
3. Convert Sorted Array to Binary Search Tree (LeetCode 108): Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

7. Templates

C++

// Basic TreeNode structure (same as above)

// Template for BST operations
class BSTTemplate {
public:
    TreeNode* root;

    BSTTemplate() : root(nullptr) {}

    // Insertion
    TreeNode* insert(TreeNode* root, int val) {
        if (!root) {
            return new TreeNode(val);
        }
        if (val < root->val) {
            root->left = insert(root->left, val);
        } else {
            root->right = insert(root->right, val);
        }
        return root;
    }

    // Search
    TreeNode* search(TreeNode* root, int val) {
        if (!root || root->val == val) {
            return root;
        }
        if (val < root->val) {
            return search(root->left, val);
        } else {
            return search(root->right, val);
        }
        return nullptr; // Not found
    }

    // Deletion (Inorder Successor Method)
    TreeNode* deleteNode(TreeNode* root, int val) {
        if (!root) return root;

        if (val < root->val)
            root->left = deleteNode(root->left, val);
        else if (val > root->val)
            root->right = deleteNode(root->right, val);
        else {
            // Node with only one child or no child
            if (!root->left) {
                TreeNode* temp = root->right;
                delete root;
                return temp;
            } else if (!root->right) {
                TreeNode* temp = root->left;
                delete root;
                return temp;
            }

            // Node with two children: Get the inorder successor
            TreeNode* successor = findMin(root->right);
            root->val = successor->val;
            root->right = deleteNode(root->right, successor->val);
        }
        return root;
    }

    // Helper function to find the minimum value node
    TreeNode* findMin(TreeNode* root) {
        TreeNode* current = root;
        while (current && current->left != nullptr)
            current = current->left;
        return current;
    }
};

Python

class TreeNode:  # Same as above
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BSTTemplate:
    def __init__(self):
        self.root = None

    def insert(self, root, val):
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root

    def search(self, root, val):
        if not root:
            return None
        if val == root.val:
            return root
        elif val < root.val:
            return self.search(root.left, val)
        else:
            return self.search(root.right, val)

    def delete(self, root, val):
        if not root:
            return None

        if val < root.val:
            root.left = self.delete(root.left, val)
        elif val > root.val:
            root.right = self.delete(root.right, val)
        else:
            if not root.left:
                return root.right
            elif not root.right:
                return root.left

            # Find Inorder Successor
            successor = self._find_min(root.right)
            root.val = successor.val
            root.right = self.delete(root.right, successor.val)

        return root

    def _find_min(self, node):
        curr = node
        while curr.left:
            curr = curr.left
        return curr

Java

class TreeNode {  // Same as above
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class BSTTemplate {
    TreeNode root;

    public BSTTemplate() {
        root = null;
    }

    public TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insert(root.left, val);
        } else {
            root.right = insert(root.right, val);
        }
        return root;
    }

    public TreeNode search(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return search(root.left, val);
        } else {
            return search(root.right, val);
        }
        return null; // Not found
    }

    public TreeNode deleteNode(TreeNode root, int val) {
        if (root == null) return root;

        if (val < root.val)
            root.left = deleteNode(root.left, val);
        else if (val > root.val)
            root.right = deleteNode(root.right, val);
        else {
            // Node with only one child or no child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Node with two children: Get the inorder successor
            root.val = findMin(root.right).val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode root) {
        TreeNode current = root;
        while (current != null && current.left != null)
            current = current.left;
        return current;
    }
}

These templates are designed to be easily copy-pasted and adapted to different problem scenarios, providing a solid foundation for BST operations. Remember to instantiate a BSTTemplate object to use its methods. Also, don’t forget the TreeNode definition. Adapt it to the specific requirements of the problem you’re solving.