DSA Binary Search Trees
A binary search tree keeps every left descendant smaller than its parent and every right descendant larger, an ordering invariant that makes search, insert, and delete all run in O(log n) time on a balanced tree.
The Binary Search Tree Invariant
A binary search tree (BST) is a binary tree that maintains one ordering rule at every node: every value in a node's left subtree must be smaller than the node's value, and every value in its right subtree must be larger. This rule holds recursively for every node in both subtrees, all the way down - not just for a node's immediate children. It's this invariant, not any particular shape, that makes a tree a BST.
The payoff is a fast lookup structure: at any node, comparing the target value against the node's value tells you which single subtree could possibly contain it, so the other subtree can be discarded entirely. On a reasonably balanced tree, this halves the remaining search space at every step, giving O(log n) search, insert, and delete - matching binary search on a sorted array for lookups, while still supporting efficient insertion and deletion that a plain array can't.
Searching and Inserting
Example: BST Search and Insert
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
self.root = self._insert(self.root, value)
def _insert(self, node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = self._insert(node.left, value)
elif value > node.value:
node.right = self._insert(node.right, value)
# equal values are ignored - no duplicates
return node
def search(self, value):
return self._search(self.root, value)
def _search(self, node, value):
if node is None:
return False
if value == node.value:
return True
if value < node.value:
return self._search(node.left, value)
return self._search(node.right, value)
tree = BST()
for n in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
tree.insert(n)
print(tree.search(6)) # True
print(tree.search(11)) # FalseDeleting a Node
Deletion is the trickiest BST operation because removing a node must not break the ordering invariant. There are three cases: deleting a leaf just removes it; deleting a node with a single child splices that child into the parent's place; and deleting a node with two children finds the in-order successor - the smallest value in the right subtree - copies that value into the node being deleted, and then deletes the successor instead, which is guaranteed to have at most one child.
Example: BST Delete
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
self.root = self._insert(self.root, value)
def _insert(self, node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = self._insert(node.left, value)
elif value > node.value:
node.right = self._insert(node.right, value)
return node
def delete(self, value):
self.root = self._delete(self.root, value)
def _delete(self, node, value):
if node is None:
return None
if value < node.value:
node.left = self._delete(node.left, value)
elif value > node.value:
node.right = self._delete(node.right, value)
else:
# Found the node to delete.
if node.left is None: # 0 or 1 child (right only)
return node.right
if node.right is None: # 1 child (left only)
return node.left
# 2 children: replace with the in-order successor
successor = node.right
while successor.left:
successor = successor.left
node.value = successor.value
node.right = self._delete(node.right, successor.value)
return node
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.value)
self._inorder(node.right, result)
tree = BST()
for n in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
tree.insert(n)
tree.delete(3) # two children -> replaced by successor 4
print(tree.inorder())
# [1, 4, 6, 7, 8, 10, 13, 14]Example: Insertion Order Doesn't Affect Sorted Output
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
self.root = self._insert(self.root, value)
def _insert(self, node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = self._insert(node.left, value)
elif value > node.value:
node.right = self._insert(node.right, value)
return node
def inorder(self):
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.value)
self._inorder(node.right, result)
import random
values = list(range(1, 21))
random.shuffle(values) # insertion order shouldn't matter
tree = BST()
for v in values:
tree.insert(v)
sorted_output = tree.inorder()
print(sorted_output)
print(sorted_output == sorted(values)) # True, regardless of insertion order- Left subtree values are always smaller than the node, right subtree values always larger
- Search, insert, and delete all follow a single path from the root toward a target position
- Average time complexity is O(log n) on a balanced tree, but O(n) in the worst case
- In-order traversal of a BST always yields values in sorted order
- Deleting a node with two children means replacing it with its in-order successor (or predecessor)
Exercise: DSA Binary Search Trees
In a binary search tree, how do values in a node's left subtree compare to that node?
