Binary Search Trees (BSTs): A Complete Guide

by

A Binary Search Tree is a type of binary tree where each node follows a specific ordering property: the left child of a node contains a value less than the node’s value, and the right child contains a value greater than the node’s value. This property makes searching, insertion, and deletion efficient.

Introduction

A Binary Search Tree (BST) is a special kind of binary tree where each node follows a specific ordering property:

  • For any given node N, all values in the left subtree of N are less than N, and all values in the right subtree are greater than N.

This property makes BSTs highly efficient for operations like searching, insertion, and deletion, typically achieving O(log n) time complexity for balanced trees.

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

BST Property:

  • Left Subtree: all values < node
  • Right Subtree: all values > node

Complete Binary Tree (CBT)

A Complete Binary Tree is a binary tree where:

  • All levels are completely filled except possibly the last level.
  • The last level has all nodes as far left as possible.
       1
     /   \
    2     3
   / \   / 
  4   5 6
Python

  • All levels are filled except the last.
  • The last level nodes (4, 5, 6) are as left as possible.

Binary Tree Representation

Linked List

A Binary Search Tree is typically represented using nodes and pointers/references, using a class or struct. Each node contains:

  • A value
  • A left pointer to the left child
  • A right pointer to the right child
class TreeNode:
    def __init__(self, val):
        self.val = val         # The node's value
        self.left = None       # Pointer to left child
        self.right = None      # Pointer to right child
Python

Then the BST itself is typically managed by a wrapper class:

class BST:
    def __init__(self):
        self.root = None       # Root node of the tree
Python

Insert values: [8, 3, 10, 1, 6, 14, 4, 7, 13]

root → TreeNode(8)
       ├── left → TreeNode(3)
       │          ├── left → TreeNode(1)
       │          └── right → TreeNode(6)
       │                      ├── left → TreeNode(4)
       │                      └── right → TreeNode(7)
       └── right → TreeNode(10)
                   └── right → TreeNode(14)
                                └── left → TreeNode(13)
Python

Array Representation (like a heap)

This is not common for BSTs because they are not complete trees. But you can store BSTs in an array using level-order indexing:

  • Use index i for a node
  • Left child at 2*i + 1
  • Right child at 2*i + 2

Not space efficient for sparse trees.

Example array (level order):

[8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13]
Python

In a complete binary tree, nodes are inserted level by level, from left to right. Let’s find how many nodes exist before each level.

  • Level 0: 1 node → indices [0]
  • Level 1: 2 nodes → indices [1, 2]
  • Level 2: 4 nodes → indices [3, 4, 5, 6]
  • Level 3: 8 nodes → indices [7, 8, ..., 14]

So the total number of nodes before level l is:

Level 0:                          A                1
                                /   \
Level 1:                     B       C             2
                            / \     / \
Level 2:                 D    E   F   G            4
                        / \  / \ / \ / \
Level 3:                H  I J K L M N O           8
SQL

At each level(l), no. of node = 2^l

Total Node


Total node(n of node) = 2^0 + 2^1 + 2^2 ......2^n-1
                      = 1 + 2 + 4 + 8 +16 ....2^n-1

It a Gp series ,sum = a(1-r^n)/(1-r)

a = 1
r = 2 

sum(Total Node) = a(1-r^n)/(1-r)
                = 1(1-r^n)(1-2)
                = 2^n-1
                
                
while n is level of tree    


Total nodes = 2^l - 1
Python

nth term (an) = a * r^(n-1) = 2^n-1
SQL

Operations on BST

Find if a value exists in the BST.

def search(root, key):
    if not root or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)
Python

Time Complexity:

  • Best/Average: O(log n)
  • Worst (unbalanced): O(n)

Insertion

Add a new node while maintaining BST property.

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

Deletion

Delete a node, with 3 possible cases:

  • Leaf node: remove directly
  • One child: replace node with child
  • Two children: find inorder successor (or predecessor) and replace
def delete(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Node with two children
        temp = find_min(root.right)
        root.val = temp.val
        root.right = delete(root.right, temp.val)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node
Python

Traversals

Inorder (LNR): Left → Node → Right

Sorted output for BST.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)
Python

Preorder (NLR): Node → Left → Right: Useful for copying tree.

Postorder (LRN): Left → Right → Node: Useful for deleting tree.

Level Order: Breadth-First Search using Queue

Time Complexity

OperationAverage CaseWorst Case (Unbalanced)
SearchO(log n)O(n)
InsertionO(log n)O(n)
DeletionO(log n)O(n)
TraversalO(n)O(n)

Implementation

Recursive approach

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

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

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

    def _insert(self, node, val):
        """Recursive insert logic."""
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        else:
            node.right = self._insert(node.right, val)
        return node

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

    def _search(self, node, val):
        """Recursive search logic."""
        if node is None or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

    def inorder(self):
        """Public inorder traversal."""
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        """Recursive inorder traversal."""
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)


    # ✅ Preorder Traversal: Node → Left → Right
    def preorder(self):
        result = []
        self._preorder(self.root, result)
        return result

    def _preorder(self, node, result):
        if node:
            result.append(node.val)
            self._preorder(node.left, result)
            self._preorder(node.right, result)

    # ✅ Postorder Traversal: Left → Right → Node
    def postorder(self):
        result = []
        self._postorder(self.root, result)
        return result

    def _postorder(self, node, result):
        if node:
            self._postorder(node.left, result)
            self._postorder(node.right, result)
            result.append(node.val)


tree = BST()
tree.insert(8)
tree.insert(3)
tree.insert(10)
tree.insert(1)
tree.insert(6)
tree.insert(14)
tree.insert(4)
tree.insert(7)
tree.insert(13)

print("Inorder Traversal:", tree.inorder())  # Output: [1, 3, 4, 6, 7, 8, 10, 13, 14]

print("Preorder  :", tree.preorder())  # [8, 3, 1, 6, 4, 7, 10, 14, 13]
print("Postorder :", tree.postorder()) # [1, 4, 7, 6, 3, 13, 14, 10, 8]


found = tree.search(6)
print("Search 6:", "Found" if found else "Not Found")  # Output: Found

found = tree.search(100)
print("Search 100:", "Found" if found else "Not Found")  # Output: Not Found
Python

Iterative approach

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

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

    # Insert a value into the BST (iterative)
    def insert(self, val):
        new_node = TreeNode(val)
        if self.root is None:
            self.root = new_node
            return

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

    # Search for a value in the BST (iterative)
    def search(self, val):
        current = self.root
        while current:
            if val == current.val:
                return True
            elif val < current.val:
                current = current.left
            else:
                current = current.right
        return False

    # Inorder traversal (iterative)
    def inorder(self):
        stack = []
        current = self.root

        while stack or current:
            # Go as left as possible
            while current:
                stack.append(current)
                current = current.left

            current = stack.pop()
            print(current.val, end=" ")
            current = current.right


tree = BST()
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    tree.insert(val)

print("Inorder traversal (sorted):")
tree.inorder()  # Output: 1 3 4 6 7 8 10 13 14

print("\nSearch 6:", tree.search(6))  # True
print("Search 100:", tree.search(100))  # False
Python

Simple Recursive approach, for competitive programming 

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

# Insert a value into the BST
def insert(node, val):
    if not node:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

# Search for a value in the BST
def search(node, val):
    if not node or node.val == val:
        return node
    if val < node.val:
        return search(node.left, val)
    else:
        return search(node.right, val)

# Inorder traversal (Left → Node → Right)
def inorder(node, res):
    if node:
        inorder(node.left, res)
        res.append(node.val)
        inorder(node.right, res)

# Preorder traversal (Node → Left → Right)
def preorder(node, res):
    if node:
        res.append(node.val)
        preorder(node.left, res)
        preorder(node.right, res)

# Postorder traversal (Left → Right → Node)
def postorder(node, res):
    if node:
        postorder(node.left, res)
        postorder(node.right, res)
        res.append(node.val)

# Find min value in BST (leftmost)
def min_value(node):
    while node and node.left:
        node = node.left
    return node

# Find max value in BST (rightmost)
def max_value(node):
    while node and node.right:
        node = node.right
    return node

# Delete a node from BST
def delete(node, val):
    if not node:
        return None
    if val < node.val:
        node.left = delete(node.left, val)
    elif val > node.val:
        node.right = delete(node.right, val)
    else:
        # Node found
        if not node.left:
            return node.right
        elif not node.right:
            return node.left
        # Node with 2 children
        min_larger_node = min_value(node.right)
        node.val = min_larger_node.val
        node.right = delete(node.right, min_larger_node.val)
    return node
    
    
 
# Build BST
root = None
for x in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, x)

# Traversals
res_in = []
inorder(root, res_in)
print("Inorder:", res_in)

res_pre = []
preorder(root, res_pre)
print("Preorder:", res_pre)

res_post = []
postorder(root, res_post)
print("Postorder:", res_post)

# Search
print("Search 6:", "Found" if search(root, 6) else "Not Found")
print("Search 100:", "Found" if search(root, 100) else "Not Found")

# Min & Max
print("Min:", min_value(root).val)
print("Max:", max_value(root).val)

# Delete a node
root = delete(root, 10)
res_after_delete = []
inorder(root, res_after_delete)
print("After deleting 10:", res_after_delete)
Python

Self-Balancing BSTs

To ensure O(log n) in all cases, self-balancing trees like:

  • AVL Trees
  • Red-Black Trees

are used in real-world systems.

Example Use Cases

  • Databases (indexing)
  • File systems (hierarchical structures)
  • Auto-complete/search suggestions
  • Memory management

Common Code Mistakes

  • Forgetting to handle edge cases in deletion
  • Not considering duplicate values (BSTs typically don’t allow them unless designed for it)
  • Assuming O(log n) without ensuring balancing

Conclusion

A Binary Search Tree is a foundational data structure that enables fast search, insert, and delete operations through its ordering property. While simple in concept, BSTs are powerful in application, especially when combined with balancing mechanisms.

Leave a Comment