Binary Search Trees (BST)

November 19, 2025
#binary-search-tree #bst #tree #data-structures #searching #algorithms #interviewing

Table of Contents

Introduction

A Binary Search Tree (BST) is a specialized binary tree with an important ordering property: for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater. This simple property enables efficient searching, insertion, and deletion operations.

BSTs are one of the most important data structures in computer science, forming the basis for efficient ordered collections, database indexing, and many algorithmic solutions. By the end of this tutorial, you’ll understand how to implement, traverse, and use BSTs effectively.

Review Binary Trees, Binary Search, and Big-O Notation first if needed.

What is a Binary Search Tree?

A BST is a binary tree with the BST property:

  • For every node N:
    • All values in the left subtree < N.value
    • All values in the right subtree > N.value
  • This property holds recursively for every node in the tree

Example of a valid BST:

       8
      / \
     3   10
    / \    \
   1   6   14
      / \  /
     4  7 13

NOT a BST (violates ordering):

       8
      / \
     3   10
    / \    \
   1  12   14  ← 12 > 8, shouldn't be in left subtree

Why use a Binary Search Tree?

Choose a BST when:

  1. You need ordered data with efficient operations
  2. You need O(log n) search in average case
  3. You need to find min/max, predecessor/successor efficiently
  4. You need range queries (find all values between x and y)
  5. You want dynamic data (unlike binary search on sorted array)
  6. You need efficient insert/delete while maintaining order

Avoid a BST when:

  • You don’t need ordering (use hash table)
  • You need guaranteed O(log n) (use self-balancing trees: AVL, Red-Black)
  • You need O(1) access by index (use array)
  • Data is mostly sequential access (use linked list)

Real-world applications

BSTs are used extensively:

  • Databases: Index structures (though usually B-trees)
  • File systems: Organizing directory structures
  • Compilers: Symbol tables for variable lookup
  • Graphics: Spatial indexing for 2D/3D scenes
  • Autocomplete: Trie-based systems (specialized BST variant)
  • Priority queues: When both ordering and dynamic updates needed
  • Game development: Storing game objects by priority
  • Network routing: Routing table lookups

BST Implementation

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // Insert a value
  insert(value) {
    const newNode = new TreeNode(value);

    if (this.root === null) {
      this.root = newNode;
      return this;
    }

    let current = this.root;
    while (true) {
      if (value === current.value) return undefined; // Duplicate
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  // Search for a value
  search(value) {
    let current = this.root;

    while (current !== null) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    return false;
  }

  // Find node with value
  find(value) {
    let current = this.root;

    while (current !== null) {
      if (value === current.value) return current;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    return null;
  }
}

// Example usage
const bst = new BinarySearchTree();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);
bst.insert(14);

console.log(bst.search(6));   // true
console.log(bst.search(12));  // false

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

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

    def insert(self, value):
        """Insert a value"""
        new_node = TreeNode(value)

        if self.root is None:
            self.root = new_node
            return self

        current = self.root
        while True:
            if value == current.value:
                return None  # Duplicate
            if value < current.value:
                if current.left is None:
                    current.left = new_node
                    return self
                current = current.left
            else:
                if current.right is None:
                    current.right = new_node
                    return self
                current = current.right

    def search(self, value):
        """Search for a value"""
        current = self.root

        while current is not None:
            if value == current.value:
                return True
            if value < current.value:
                current = current.left
            else:
                current = current.right

        return False

    def find(self, value):
        """Find node with value"""
        current = self.root

        while current is not None:
            if value == current.value:
                return current
            if value < current.value:
                current = current.left
            else:
                current = current.right

        return None

# Example usage
bst = BinarySearchTree()
bst.insert(8)
bst.insert(3)
bst.insert(10)
bst.insert(1)
bst.insert(6)
bst.insert(14)

print(bst.search(6))   # True
print(bst.search(12))  # False

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    // Insert a value
    public void insert(int value) {
        TreeNode newNode = new TreeNode(value);

        if (root == null) {
            root = newNode;
            return;
        }

        TreeNode current = root;
        while (true) {
            if (value == current.value) return; // Duplicate
            if (value < current.value) {
                if (current.left == null) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (current.right == null) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }

    // Search for a value
    public boolean search(int value) {
        TreeNode current = root;

        while (current != null) {
            if (value == current.value) return true;
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        return false;
    }

    // Find node with value
    public TreeNode find(int value) {
        TreeNode current = root;

        while (current != null) {
            if (value == current.value) return current;
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(8);
        bst.insert(3);
        bst.insert(10);
        bst.insert(1);
        bst.insert(6);
        bst.insert(14);

        System.out.println(bst.search(6));   // true
        System.out.println(bst.search(12));  // false
    }
}

Common BST operations

Finding minimum and maximum

class BinarySearchTree {
  // ... previous code

  findMin(node = this.root) {
    if (node === null) return null;
    while (node.left !== null) {
      node = node.left;
    }
    return node.value;
  }

  findMax(node = this.root) {
    if (node === null) return null;
    while (node.right !== null) {
      node = node.right;
    }
    return node.value;
  }
}

console.log(bst.findMin());  // 1
console.log(bst.findMax());  // 14

class BinarySearchTree:
    # ... previous code

    def find_min(self, node=None):
        if node is None:
            node = self.root
        if node is None:
            return None
        while node.left is not None:
            node = node.left
        return node.value

    def find_max(self, node=None):
        if node is None:
            node = self.root
        if node is None:
            return None
        while node.right is not None:
            node = node.right
        return node.value

print(bst.find_min())  # 1
print(bst.find_max())  # 14

public class BinarySearchTree {
    // ... previous code

    public Integer findMin() {
        if (root == null) return null;
        TreeNode node = root;
        while (node.left != null) {
            node = node.left;
        }
        return node.value;
    }

    public Integer findMax() {
        if (root == null) return null;
        TreeNode node = root;
        while (node.right != null) {
            node = node.right;
        }
        return node.value;
    }
}

System.out.println(bst.findMin());  // 1
System.out.println(bst.findMax());  // 14

Deleting a node

Deletion is the most complex operation in a BST. Three cases:

  1. Leaf node (no children): Simply remove
  2. One child: Replace node with its child
  3. Two children: Replace with in-order successor (or predecessor), then delete successor
class BinarySearchTree {
  // ... previous code

  delete(value) {
    this.root = this.deleteNode(this.root, value);
    return this;
  }

  deleteNode(node, value) {
    if (node === null) return null;

    if (value < node.value) {
      node.left = this.deleteNode(node.left, value);
      return node;
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value);
      return node;
    } else {
      // Found the node to delete

      // Case 1: Leaf node
      if (node.left === null && node.right === null) {
        return null;
      }

      // Case 2: One child
      if (node.left === null) return node.right;
      if (node.right === null) return node.left;

      // Case 3: Two children
      // Find in-order successor (min in right subtree)
      let successor = node.right;
      while (successor.left !== null) {
        successor = successor.left;
      }

      // Replace node's value with successor's value
      node.value = successor.value;

      // Delete the successor
      node.right = this.deleteNode(node.right, successor.value);

      return node;
    }
  }
}

bst.delete(3);
console.log(bst.search(3));  // false

class BinarySearchTree:
    # ... previous code

    def delete(self, value):
        self.root = self._delete_node(self.root, value)
        return self

    def _delete_node(self, node, value):
        if node is None:
            return None

        if value < node.value:
            node.left = self._delete_node(node.left, value)
            return node
        elif value > node.value:
            node.right = self._delete_node(node.right, value)
            return node
        else:
            # Found the node to delete

            # Case 1: Leaf node
            if node.left is None and node.right is None:
                return None

            # Case 2: One child
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left

            # Case 3: Two children
            # Find in-order successor (min in right subtree)
            successor = node.right
            while successor.left is not None:
                successor = successor.left

            # Replace node's value with successor's value
            node.value = successor.value

            # Delete the successor
            node.right = self._delete_node(node.right, successor.value)

            return node

bst.delete(3)
print(bst.search(3))  # False

public class BinarySearchTree {
    // ... previous code

    public void delete(int value) {
        root = deleteNode(root, value);
    }

    private TreeNode deleteNode(TreeNode node, int value) {
        if (node == null) return null;

        if (value < node.value) {
            node.left = deleteNode(node.left, value);
            return node;
        } else if (value > node.value) {
            node.right = deleteNode(node.right, value);
            return node;
        } else {
            // Found the node to delete

            // Case 1: Leaf node
            if (node.left == null && node.right == null) {
                return null;
            }

            // Case 2: One child
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            // Case 3: Two children
            // Find in-order successor (min in right subtree)
            TreeNode successor = node.right;
            while (successor.left != null) {
                successor = successor.left;
            }

            // Replace node's value with successor's value
            node.value = successor.value;

            // Delete the successor
            node.right = deleteNode(node.right, successor.value);

            return node;
        }
    }
}

bst.delete(3);
System.out.println(bst.search(3));  // false

Validating a BST

Check if a binary tree satisfies the BST property:

function isValidBST(node, min = -Infinity, max = Infinity) {
  if (node === null) return true;

  // Current node must be within the valid range
  if (node.value <= min || node.value >= max) {
    return false;
  }

  // Recursively check left and right subtrees
  return isValidBST(node.left, min, node.value) &&
         isValidBST(node.right, node.value, max);
}

console.log(isValidBST(bst.root));  // true

def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
    if node is None:
        return True

    # Current node must be within the valid range
    if node.value <= min_val or node.value >= max_val:
        return False

    # Recursively check left and right subtrees
    return (is_valid_bst(node.left, min_val, node.value) and
            is_valid_bst(node.right, node.value, max_val))

print(is_valid_bst(bst.root))  # True

public static boolean isValidBST(TreeNode node) {
    return isValidBSTHelper(node, Long.MIN_VALUE, Long.MAX_VALUE);
}

private static boolean isValidBSTHelper(TreeNode node, long min, long max) {
    if (node == null) return true;

    // Current node must be within the valid range
    if (node.value <= min || node.value >= max) {
        return false;
    }

    // Recursively check left and right subtrees
    return isValidBSTHelper(node.left, min, node.value) &&
           isValidBSTHelper(node.right, node.value, max);
}

System.out.println(isValidBST(bst.root));  // true

In-order traversal gives sorted order

inOrder(node = this.root, result = []) {
  if (node !== null) {
    this.inOrder(node.left, result);
    result.push(node.value);
    this.inOrder(node.right, result);
  }
  return result;
}

console.log(bst.inOrder());  // [1, 6, 8, 10, 14] (sorted!)

def in_order(self, node=None, result=None):
    if result is None:
        result = []
    if node is None:
        node = self.root

    if node is not None:
        self.in_order(node.left, result)
        result.append(node.value)
        self.in_order(node.right, result)

    return result

print(bst.in_order())  # [1, 6, 8, 10, 14] (sorted!)

public List<Integer> inOrder(TreeNode node, List<Integer> result) {
    if (result == null) result = new ArrayList<>();
    if (node != null) {
        inOrder(node.left, result);
        result.add(node.value);
        inOrder(node.right, result);
    }
    return result;
}

System.out.println(bst.inOrder(bst.root, null));
// [1, 6, 8, 10, 14] (sorted!)

Complexity analysis

Operation Average Case Worst Case Best Case
Search O(log n) O(n) O(1)
Insert O(log n) O(n) O(1)
Delete O(log n) O(n) O(1)
Find Min/Max O(log n) O(n) O(1)
In-order Traversal O(n) O(n) O(n)
Space O(n) O(n) O(n)

Key insight: Worst case O(n) occurs when the tree becomes skewed (essentially a linked list). This happens with sorted or reverse-sorted insertions.

Solution: Use self-balancing BSTs (AVL trees, Red-Black trees) to guarantee O(log n) operations.

BST vs other data structures

Feature BST Hash Table Sorted Array
Search O(log n) avg O(1) avg O(log n)
Insert O(log n) avg O(1) avg O(n)
Delete O(log n) avg O(1) avg O(n)
Ordered ✅ Yes ❌ No ✅ Yes
Min/Max O(log n) O(n) O(1)
Range queries ✅ Efficient ❌ Inefficient ✅ Efficient
Successor/Predecessor O(log n) ❌ N/A O(1)

Common pitfalls

  • Not handling duplicates: Decide whether to allow duplicates or reject them
  • Unbalanced trees: Without balancing, BST degrades to O(n)
  • Incorrect deletion: The two-children case is tricky—test thoroughly
  • Validation errors: When validating, must check entire subtree ranges, not just children
  • Memory leaks: In manual-memory languages, ensure deleted nodes are freed
  • Integer overflow: When using min/max bounds in validation

When to prefer other data structures

  • Need guaranteed O(log n) → Use AVL tree or Red-Black tree
  • Don’t need ordering → Use hash table
  • Need O(1) access by index → Use array
  • Data is mostly insertions at ends → Use deque
  • Need priority-based access → Use heap (min-heap or max-heap)

Practice problems

  1. Find the kth smallest element in a BST
  2. Convert a sorted array to a balanced BST
  3. Find the lowest common ancestor (LCA) of two nodes in a BST
  4. Check if two BSTs are identical
  5. Find the in-order successor of a given node
  6. Convert a BST to a sorted doubly linked list
  7. Find the distance between two nodes in a BST
  8. Serialize and deserialize a BST
  9. Find all nodes in a given range [k1, k2]
  10. Recover a BST where two nodes are swapped by mistake
  11. Implement an iterator for BST (in-order traversal)
  12. Find the closest value to a target in a BST
  13. Count the number of BSTs that can be formed with n nodes
  14. Merge two BSTs into one balanced BST
  15. Find the mode (most frequent element) in a BST

Complexity summary

  • Time complexity:
    • Search, Insert, Delete: O(log n) average, O(n) worst (skewed)
    • Find Min/Max: O(log n) average, O(n) worst
    • Traversal: O(n) always
  • Space complexity:
    • Storage: O(n) for n nodes
    • Recursion stack: O(h) where h is height (O(log n) balanced, O(n) skewed)

Binary Search Trees combine the benefits of binary search with dynamic insertion and deletion. While basic BSTs can degrade to O(n) operations, they form the foundation for self-balancing variants (AVL, Red-Black) that guarantee O(log n) performance.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor