A Binary Search Tree (BST) is a binary tree where each node’s left subtree contains smaller values, and the right subtree contains larger values. This ordering allows efficient searching, insertion and deletion.
In this chapter you will learn
A Binary Search Tree (BST) is a special kind of binary tree where each node satisfies the BST property:
This property is applied recursively to every node in the tree. Because of this ordering, we can search for values efficiently, similar to binary search on a sorted array.
This is a valid BST because for every node, all nodes in the left subtree are smaller, and all nodes in the right subtree are larger.
BSTs provide efficient searching, insertion, and deletion of values while maintaining a sorted order. This makes them useful for dynamic datasets where frequent updates are needed.
Key benefits of using a BST include:
Some drawbacks of BSTs are:
| Operation | Average | Worst (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Traverse (any) | O(n) | O(n) |
Each node in a BST contains a value and references to its left and right children.
When inserting a value into a BST, we compare it with the current node:
value < node.value → go to the left subtreevalue >= node.value → go to the right subtreeSearching follows the same path as insertion: compare the target with the current node and go left or right accordingly. If we find the value, return True; if we reach None, return False.
def search(self, value):
return self._search(self.root, value)
def _search(self, node, value):
if not node:
return False
if value == node.value:
return True
if value < node.value:
return self._search(node.left, value)
else:
return self._search(node.right, value)Average time complexity: O(log n), but O(n) in a skewed tree.
Tree traversals define the order in which we visit the nodes of a tree. For BSTs, in-order traversal is especially important because it yields values in sorted order.
For a BST, in-order traversal prints values in ascending sorted order.
def inorder(self):
self._inorder(self.root)
def _inorder(self, node):
if node:
self._inorder(node.left)
print(node.value)
self._inorder(node.right)Used to copy or serialize the tree structure.
def preorder(self):
self._preorder(self.root)
def _preorder(self, node):
if node:
print(node.value)
self._preorder(node.left)
self._preorder(node.right)Useful when deleting or freeing the tree from memory.
def postorder(self):
self._postorder(self.root)
def _postorder(self, node):
if node:
self._postorder(node.left)
self._postorder(node.right)
print(node.value)Deletion in a BST is the most complex operation. There are three main cases:
Simply remove the node.
Just remove the node.
Replace the node with its single child.
Replace the node with its single child.
Steps:
def delete(self, value):
self.root = self._delete(self.root, value)
def _delete(self, node, value):
if not node:
return node
# Search down the tree
if value < node.value:
node.left = self._delete(node.left, value)
elif value > node.value:
node.right = self._delete(node.right, value)
else:
# Node found
# CASE 1: No children
if not node.left and not node.right:
return None
# CASE 2: One child
if not node.left:
return node.right
if not node.right:
return node.left
# CASE 3: Two children
successor = self._min_value(node.right)
node.value = successor
node.right = self._delete(node.right, successor)
return node
def _min_value(self, node):
while node.left:
node = node.left
return node.value
The performance of BST operations depends on the tree's height.
A balanced BST has a height of about log₂(n),
while an unbalanced BST can degenerate into a linked list with height n.
The height is about log₂(n), so operations are fast: O(log n).
In the worst case, inserting sorted data creates a skewed tree:
This behaves like a linked list. Search, insert and delete can become O(n). To prevent this, self-balancing trees like AVL and Red-Black trees are used in practice.
Here is the complete implementation of a Binary Search Tree in Python, along with example usage:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
# ---------- INSERT ----------
def insert(self, value):
if not self.root:
self.root = Node(value)
return
self._insert(self.root, value)
def _insert(self, node, value):
if value < node.value:
if node.left:
self._insert(node.left, value)
else:
node.left = Node(value)
else:
if node.right:
self._insert(node.right, value)
else:
node.right = Node(value)
# ---------- SEARCH ----------
def search(self, value):
return self._search(self.root, value)
def _search(self, node, value):
if not node:
return False
if value == node.value:
return True
if value < node.value:
return self._search(node.left, value)
else:
return self._search(node.right, value)
# ---------- TRAVERSALS ----------
def inorder(self):
self._inorder(self.root)
def _inorder(self, node):
if node:
self._inorder(node.left)
print(node.value)
self._inorder(node.right)
def preorder(self):
self._preorder(self.root)
def _preorder(self, node):
if node:
print(node.value)
self._preorder(node.left)
self._preorder(node.right)
def postorder(self):
self._postorder(self.root)
def _postorder(self, node):
if node:
self._postorder(node.left)
self._postorder(node.right)
print(node.value)
# ---------- DELETE ----------
def delete(self, value):
self.root = self._delete(self.root, value)
def _delete(self, node, value):
if not node:
return node
if value < node.value:
node.left = self._delete(node.left, value)
elif value > node.value:
node.right = self._delete(node.right, value)
else:
# No children
if not node.left and not node.right:
return None
# One child
if not node.left:
return node.right
if not node.right:
return node.left
# Two children
successor = self._min_value(node.right)
node.value = successor
node.right = self._delete(node.right, successor)
return node
def _min_value(self, node):
while node.left:
node = node.left
return node.value# Example Usage:
bst = BST()
for value in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(value)
print("In-order (sorted):")
bst.inorder() # 20 30 40 50 60 70 80
print("Search 60:", bst.search(60)) # True
print("Search 100:", bst.search(100)) # False
bst.delete(70)
print("After deleting 70:")
bst.inorder()This class provides a full implementation of a Binary Search Tree with insertion, searching, deletion, and various tree traversals.
You can create a BST instance, insert values, search for values, delete nodes, and traverse the tree in different orders.
Test code here:
Binary Search Trees are widely used in various applications, including:
Understanding BSTs is a crucial step toward mastering advanced data structures used in real-world systems.