Binary Search Tree

A detailed yet simple explanation of the Binary Search Tree (BST) data structure.

What is a Binary Search Tree?

A Binary Search Tree (BST) is a special type of Binary Tree where the nodes are arranged in a specific order:

  • The left child of a node contains values smaller than the node’s value.
  • The right child of a node contains values greater than the node’s value.

This ordering property allows for efficient searching, insertion, and deletion operations. It is like a "sorted" Binary Tree, making it easy to search for values by comparing each node’s value and moving left or right based on whether the target value is smaller or larger.

How a Binary Search Tree Works

The key to understanding a Binary Search Tree is the ordering rule:

  • At each node, I compare the target value with the node’s value.
    • If the target is smaller, I move to the left child.
    • If the target is larger, I move to the right child.

This continues recursively until I find the target value or reach a leaf node (a node with no children). If the value is not found, I know it doesn’t exist in the tree.

Here’s an example of a simple Binary Search Tree:

  • The root node is 10.
  • 5 is less than 10, so it goes to the left.
  • 15 is greater than 10, so it goes to the right.
  • The same comparison applies recursively for each node.

Operations on a Binary Search Tree

Here are the key operations and their time complexities in a Binary Search Tree:

  1. Insertion: Add a new node while maintaining BST property

    • Average Case: O(log n) for balanced trees
    • Worst Case: O(n) for skewed trees

  2. Searching: Find a specific value

    • Average Case: O(log n) for balanced trees
    • Worst Case: O(n) for skewed trees

  3. Deletion: Remove a node while maintaining BST property

    • Average Case: O(log n) for balanced trees
    • Worst Case: O(n) for skewed trees

  4. Traversal: Visit all nodes in specific order

    • In-order, Pre-order, Post-order: O(n)

  5. Finding Minimum/Maximum:

    • Time Complexity: O(h) where h is height
    • Best Case (balanced): O(log n)
    • Worst Case (skewed): O(n)

  6. Finding Height: Calculate number of levels

    • Time Complexity: O(n)
    • Space Complexity: O(h) for recursive approach

Note: The efficiency of BST operations heavily depends on the tree's balance. A balanced BST performs significantly better than a skewed one.

Insertion in a Binary Search Tree

When inserting a node, I follow these steps:

  • Start at the root and compare the value to be inserted with the current node.
  • If the value is smaller, move left; if larger, move right.
  • Repeat this process recursively until I find an empty spot (null) where the new node can be inserted.

Deletion in a Binary Search Tree

When deleting a node, there are three possible cases:

  1. Node has no children: Simply remove the node.
  2. Node has one child: Replace the node with its child.
  3. Node has two children: Find the in-order successor (the smallest value node in the right subtree) or in-order predecessor (the largest value node in the left subtree), replace the node with that value, and then delete the successor or predecessor.

Code Examples

Let’s look at how I can implement basic operations like insertion and in-order traversal in C++, Python, and Java.

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

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

    # Insert a node into the binary search tree
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    # Helper function to insert a node recursively
    def _insert(self, root, value):
        if value < root.data:
            if root.left is None:
                root.left = Node(value)
            else:
                self._insert(root.left, value)
        else:
            if root.right is None:
                root.right = Node(value)
            else:
                self._insert(root.right, value)

    # In-order traversal of the tree
    def in_order(self):
        self._in_order(self.root)

    def _in_order(self, root):
        if root:
            self._in_order(root.left)
            print(root.data, end=" ")
            self._in_order(root.right)

# Example usage
tree = BinarySearchTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(3)
tree.insert(7)

print("In-order traversal: ", end="")
tree.in_order()  # Should print 3 5 7 10 15
print()

Problems to Solve

Important Problems on Trees

Resources