PYTHON / DATA STRUCTURES AND ALGORITHMS
Binary search trees
Build, search, and delete keys in a binary search tree in Python, and explain why insertion order decides whether lookups cost log n or n.
What you will learn
- Insert and search a BST iteratively, following one root-to-leaf path
- Produce sorted keys with an in-order traversal of the tree
- Delete a node with two children by promoting its in-order successor
- Recognise degenerate trees and measure height to explain slow lookups
Understanding Binary search trees
A binary search tree stores one key per node with an invariant that covers whole subtrees, not just immediate children: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. That subtree-wide guarantee is what makes searching work. When you compare your target with a node and it is smaller, you can discard the entire right subtree in one comparison, because the invariant promises nothing smaller lives there.
Because each comparison drops one side, a search touches at most one node per level, so its cost is proportional to the tree's height, not its size. Height is not something the BST controls for you. Inserting keys in ascending order sends every new key down the right spine, producing a chain of n nodes where lookups become linear scans; inserting the same keys in a shuffled or median-first order yields a height near log2(n). This is why plain BSTs are the starting point for self-balancing variants like AVL and red-black trees, which do extra work on insert to keep height bounded.
In-order traversal (left subtree, node, right subtree) visits keys in ascending order, which is the direct consequence of the invariant and the cheapest way to check your tree is well formed. Deletion is the only awkward operation: a leaf just detaches, a node with one child is replaced by that child, but a node with two children must be filled by its in-order successor, the smallest key in its right subtree, because that is the only key that preserves the invariant on both sides. Python's standard library ships no BST type, so hand-rolling one is the normal way to learn it; production code usually reaches for a sorted list with bisect or an external sorted-container package.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
cur = root
while True:
if key < cur.key:
if cur.left is None:
cur.left = Node(key)
return root
cur = cur.left
elif key > cur.key:
if cur.right is None:
cur.right = Node(key)
return root
cur = cur.right
else:
return root # duplicate key: ignore
def contains(root, key):
cur = root
compares = 0
while cur is not None:
compares += 1
if key == cur.key:
return True, compares
cur = cur.left if key < cur.key else cur.right
return False, compares
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.key)
inorder(node.right, out)
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 30]:
root = insert(root, k)
keys = []
inorder(root, keys)
print("in-order:", keys)
print("find 60:", contains(root, 60))
print("find 65:", contains(root, 65))A BST's ordering invariant applies to entire subtrees, so each comparison discards half the remaining structure and search costs the tree's height.
Worked examples
Sorted input destroys the tree
Shows that the same seven keys give height 7 or height 3 depending only on insertion order.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
def build(keys):
root = None
for k in keys:
root = insert(root, k)
return root
def right_spine(node):
out = []
while node is not None:
out.append(node.key)
node = node.right
return out
ascending = build([1, 2, 3, 4, 5, 6, 7])
median_first = build([4, 2, 6, 1, 3, 5, 7])
print("heights:", height(ascending), height(median_first))
print("right spine of ascending:", right_spine(ascending))Example explained
Line 1The recursive insert returns the (possibly new) subtree root, so the caller must reassign root.left or root.right.
Line 2Each ascending key is larger than everything already stored, so it is appended to the right spine and no left child ever exists.
Line 3height(ascending) is 7 for 7 keys: a search for 7 compares against every node, which is a linear scan.
Line 4Inserting the median 4 first, then the medians of each half, gives height 3, close to the log2(7) ideal.
Deleting a node with two children
Demonstrates promoting the in-order successor so the ordering invariant survives the deletion.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def delete(root, key):
if root is None:
return None
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
succ = root.right
while succ.left is not None:
succ = succ.left
root.key = succ.key
root.right = delete(root.right, succ.key)
return root
def inorder(node):
if node is None:
return []
return inorder(node.left) + [node.key] + inorder(node.right)
root = None
for k in [50, 30, 70, 60, 80, 65]:
root = insert(root, k)
root = delete(root, 70)
print("root and its right child:", root.key, root.right.key)
print("in-order:", inorder(root))Example explained
Line 1The node holding 70 has both children, so it cannot simply be unlinked without orphaning a subtree.
Line 2succ walks to the leftmost node of the right subtree; here 80 has no left child, so 80 itself is the successor.
Line 3Copying 80 into the node and then deleting 80 from the right subtree reduces the hard case to an easy one, since a successor never has a left child.
Line 4The in-order list is still ascending, which is the proof that the invariant held through the deletion.
Checking parent only is not enough
Shows a tree that passes a local parent-child check but is not a BST, so search misses a key that is present.
import math
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
# 8 sits in the right subtree of 10, but 8 < 10
bad = Node(10, Node(5), Node(15, Node(8), Node(20)))
def locally_ok(node):
if node is None:
return True
if node.left is not None and node.left.key > node.key:
return False
if node.right is not None and node.right.key < node.key:
return False
return locally_ok(node.left) and locally_ok(node.right)
def is_bst(node, low=-math.inf, high=math.inf):
if node is None:
return True
if not low < node.key < high:
return False
return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)
def contains(node, key):
while node is not None:
if key == node.key:
return True
node = node.left if key < node.key else node.right
return False
print(locally_ok(bad), is_bst(bad), contains(bad, 8))Example explained
Line 1locally_ok returns True because 8 is legitimately smaller than its parent 15; the parent check never sees the ancestor 10.
Line 2is_bst carries a (low, high) window down the tree, so when it reaches 8 with low=10 the test 10 < 8 fails.
Line 3contains(bad, 8) goes left at 10 and never enters the subtree holding 8, so a key that is physically in the tree is unreachable.
Line 4This is why the invariant must be stated over subtrees: search depends on it, not just on parent-child order.
Important notes
Recursive traversals hit Python's default recursion limit near 1000 frames, so a skewed tree of a few thousand keys raises RecursionError even though an iterative search on it would only be slow.
Decide a duplicate policy up front: ignoring duplicates, keeping a count per node, or always pushing them right all produce different traversal results.
Common mistakes
Using a recursive insert that returns a node but ignoring the return value, so root stays None and every insert is silently thrown away.
Checking only parent against child when validating or rebuilding a tree, producing a structure where search skips keys that are actually stored.
Loading already-sorted data (IDs, timestamps) into a plain BST, which builds a one-sided chain and turns every lookup into an O(n) scan while looking like it worked.
Try it yourself
Change, predict, then run
Extend the main example with range_keys(root, lo, hi) that returns the sorted keys in [lo, hi], skipping the left subtree when node.key < lo and the right subtree when node.key > hi. Test that range_keys(root, 35, 65) returns [40, 50, 60].
Open the Python workspaceCheck your understanding
You insert the integers 1 through 1000 in ascending order into a plain (unbalanced) BST, then search for 1000. Roughly how many nodes does the search visit?
- About 10, because binary search on 1000 items is logarithmic
- About 1000, because ascending inserts build a right-leaning chain
- About 500, because the search starts from the middle of the key range
- Exactly 1, because 1000 is the largest key and ends up at the root
Show answer
Each new key is larger than every existing key, so it becomes the right child of the deepest node; the tree is a 1000-node chain and reaching 1000 visits all of them. The logarithmic answer assumes a balanced tree, which a plain BST does not maintain, and the root is fixed as the first key inserted (1), never the largest.