ReviseAlgo Logo

Trees

Binary Search Tree

Master Binary Search Tree (BST) operations: insertion, search, and deletion (3 cases) with balanced vs skewed analysis.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is a Binary Search Tree (BST)?

A Binary Search Tree is a node-based binary tree data structure which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • The left and right subtrees must each also be a binary search tree.

    • Why is it Important?

    This sorted invariant allows you to bypass half of the tree during each comparison. In a balanced BST, lookup, insertion, and deletion take O(log N) logarithmic time, mirroring binary search arrays but supporting dynamic adjustments.

    Where is it Used?

  • Database Indexes: Maintaining sorted indexes of primary keys to support range queries.
  • Set Implementations: Supporting sorted collection APIs (like Java's TreeSet or C++'s std::set).

    • 2. Mental Model: The Sorted Phone Book

    Imagine searching for a contact in a phone book:

  • You open the book to the middle.
  • If the target name is alphabetically smaller than the middle name, you ignore the entire right half of the book.
  • You repeat this process recursively on the left half.
  • In a BST, every node represents a "middle page" of a section, pointing left for earlier letters and right for later letters.

    • 3. Core BST Operations & Implementations

    BST Deletion Cases

    1. Case 1: Node is a Leaf: Simply delete the node (return null). 2. Case 2: Node has One Child: Bypass the node, connecting its parent directly to its child (return the non-null child). 3. Case 3: Node has Two Children: Find the In-order Successor (the smallest node in the right subtree). Copy its value to the target node, then recursively delete the in-order successor from the right subtree.

    4. Visual Trace: Deleting a Node with Two Children

    Let's delete node 20 from the tree below (Case 3):

    5. Real-World Examples

  • Memory Segment Trees: Managing allocation blocks dynamically using trees to speed up searches.
  • High-Frequency Trading Engines: Storing transaction queues inside self-balancing BSTs (like Red-Black trees) to fetch min/max bids instantly.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test validation and pointer tracking:
  • "Given a binary tree, check if it is a valid BST." -> You cannot just compare a node with its immediate children. A node's left child must be less than the parent, but all nodes in its left subtree must also be less than it. Use a recursive bounds check passing [min, max] intervals down:
    • isValid(node, \min, \max) \implies \min < node.val < \max
  • "Find the in-order successor of a node in a BST." -> If the node has a right child, the successor is the minimum node in that right subtree. Otherwise, it is the lowest ancestor that branches right.

    • Common Mistakes

    Warning: 1. Wrong BST Validation: Checking only root.left.val < root.val < root.right.val recursively. This is incorrect. Consider: [10, 5, 15, null, null, 6, 20]. Here, 6 is a left child of 15, but 6 is smaller than the root 10, violating the global BST invariant.
    > 2. Skewed BST Complexity: Assuming BST search is always O(log N). If elements are inserted in sorted order (e.g. 1, 2, 3, 4), the BST becomes skewed, degrading operations to O(N) linear time.

    7. Summary

  • BST Invariant: Left subtree < node < right subtree.
  • In-order Traversal: Traverses BST keys in sorted ascending order.
  • Three Deletion Cases: Free leaf, bypass single child, or swap value with in-order successor.
  • Complexities: Balanced is O(log N) time, skewed is O(N) time.

    • 8. Quiz

    Question 1: What is the time complexity of searching in a perfectly balanced BST of size N? Answer: O(log N) time. At each step, we discard exactly half of the remaining search space.
    Question 2: What is the in-order predecessor of a node in a BST? Answer: The largest element in the node's left subtree. It is found by going left once, then right as far as possible.
    Question 3: If you insert elements in the order [5, 3, 8, 2, 4, 7, 9], what is the value of the root node? Answer: 5. The first element inserted into an empty BST always becomes the permanent root node.
    Question 4: True or False: Every binary search tree is balanced. Answer: False. BSTs only guarantee key sorting, not height balancing. Self-balancing variations (like AVL or Red-Black trees) are required to guarantee balance.
    Question 5: What is the complexity of validating a BST of N nodes? Answer: O(N) time, since we must visit each of the N nodes exactly once to verify they satisfy their respective range boundaries.