Data structures in Python

Binary Search Tree Lab

Code a BST from scratch. Step through insert, search and delete, the three depth-first traversals and the height, and watch the call stack grow and shrink as the recursion runs.

The BST property

#           50
#         /    \
#       30      70
#      /  \    /  \
#    20   40  60   80
#         /
#       35

For every node, everything in its left subtree is smaller and everything in its right subtree is larger. The whole subtree, not just the child: 35 sits under 40, but it is also in 30's right subtree and 50's left subtree, so it must be greater than 30 and less than 50.

Two small classes

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None    # smaller values
        self.right = None   # larger values

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

A node holds a value and two links. The tree only remembers its root; everything else is reached by following links down. An empty subtree is just None.

Duplicates: pick a rule

tree.insert(40)
tree.insert(40)   # ignored: 40 is already there

This lab treats the tree like a set and ignores a value that is already present. Other common rules: keep a count in each node, or always send equal values the same way (say, right with >=). Any rule works if search and delete follow the same one.

Words you will need

root     the top node (50), no parent
leaf     a node with no children (20, 35, 60, 80)
subtree  a node plus everything below it
depth    edges from the root down to a node
height   edges on the longest path down to a leaf

In the example, 35 has depth 3, and the whole tree has height 3. The height is what decides how fast a BST is, so it gets its own operation and section below.

Recursive or loop?

Insert, search and delete follow one path down, so a loop works and needs only O(1) extra memory. The lab uses recursion for insert and delete because the return the subtree, assign it back pattern is short and handles every case, and a loop for search. Traversals and height must visit both children of every node, so recursion is the natural fit there.

Every recursive call is a frame on the call stack, so recursion uses O(h) extra memory. The lab draws that stack next to the tree.

def insert(self, value):         # loop version
    new = Node(value)
    if self.root is None:
        self.root = new
        return
    node = self.root
    while True:
        if value < node.value:
            if node.left is None:
                node.left = new
                return
            node = node.left
        elif value > node.value:
            if node.right is None:
                node.right = new
                return
            node = node.right
        else:
            return                # duplicate

current nodeon the path down / waiting on the call stackdone: output or finishedabout to be unlinkedan empty child (None)local variable (node, succ)returned height

Tip: the ← and → keys step too. Nodes are drawn left to right in sorted order, so a node's position across the page is its rank.

Max height and why it matters

Insert, search and delete each walk one path from the root down, so they cost O(h), where h is the height. That makes the height, not the number of nodes, the number that decides how fast a BST is. And the height depends entirely on the order the values arrived in.

The same 7 values, inserted in two different orders

40, 20, 60, 10, 30, 50, 70
middle first: height 2, the minimum, ⌊log₂ 7⌋

10, 20, 30, 40, 50, 60, 70
sorted: height 6, the maximum, n − 1

Sorted input sends every new value to the right of the last one, so the "tree" is a linked list leaning right. Searching it is a linear scan. Try Build from a list above with the presets to watch both shapes grow.

Height bounds for n nodes (edges on the longest root-to-leaf path)
n	Best: ⌊log₂ n⌋	Worst: n − 1
7	2	6
15	3	14
1,000	9	999
1,000,000	19	999,999

Why ⌊log₂ n⌋ is the minimum. Level d holds at most 2^d nodes, so a tree of height h holds at most 2^h+1 − 1. Fitting n nodes needs h ≥ log₂(n + 1) − 1, which rounds up to ⌊log₂ n⌋.
Random order is usually fine. Values inserted in a random order give a height of O(log n) on average. Sorted or nearly sorted input, which real data often is, gives the worst case.
Deep trees break recursion. Python stops at about 1,000 nested calls. A skewed tree of 5,000 nodes makes the recursive height, inorder or _insert raise RecursionError; the loop versions still work.
The fix is to rebalance as you go. Self-balancing trees such as AVL trees and red-black trees rotate nodes after each insert and delete to keep h = O(log n) whatever the input order.

Counting edges (this lab)

def height(self, node):
    if node is None:
        return -1
    return 1 + max(self.height(node.left),
                   self.height(node.right))
# empty: -1   one node: 0   example tree: 3

Counting nodes ("max depth")

def max_depth(self, node):
    if node is None:
        return 0
    return 1 + max(self.max_depth(node.left),
                   self.max_depth(node.right))
# empty: 0    one node: 1   example tree: 4

Both are correct; they differ by exactly 1. Textbooks usually mean edges when they say height. Many coding problems ask for "maximum depth" and mean nodes. Check which one a question wants, and only the base case changes.

Common mistakes

Checking only the children

def is_bst(node):
    if node is None:
        return True
    if node.left and node.left.value >= node.value:
        return False
    if node.right and node.right.value <= node.value:
        return False
    return is_bst(node.left) and is_bst(node.right)

def is_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None:
        return True
    if not lo < node.value < hi:
        return False
    return (is_bst(node.left, lo, node.value) and
            is_bst(node.right, node.value, hi))

Change 40 to 60 in the example tree. Every parent and child pair still looks fine (60 > 30, 35 < 60), but 60 is in 50's left subtree, so the tree is broken. Pass down the range each subtree must stay inside, or check that inorder is strictly increasing.

Dropping the recursive result

def _insert(self, node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        self._insert(node.left, value)   # result lost
    elif value > node.value:
        self._insert(node.right, value)  # result lost
    # forgot: return node

    if value < node.value:
        node.left = self._insert(node.left, value)
    elif value > node.value:
        node.right = self._insert(node.right, value)
    return node

The new Node is returned into thin air, so nothing is ever linked. Forget return node and every caller stores None, cutting off whole subtrees. The same goes for self.root = self._insert(self.root, value): without it, inserting into an empty tree does nothing. Delete has the identical trap.

Mixing up the traversal orders

# the name says where the node goes
preorder:  node, left, right  # 50 30 20 40 35 70 60 80
inorder:   left, node, right  # 20 30 35 40 50 60 70 80
postorder: left, right, node  # 20 35 40 30 60 80 70 50

All three walk the tree identically; only the position of out.append moves. Quick checks: inorder of a BST is sorted, preorder starts with the root, postorder ends with it. Run All three in one walk above to see them side by side.

Height off by one

def height(self, node):
    if node is None:
        return 0           # counts nodes...
    return 1 + max(self.height(node.left),
                   self.height(node.right))
# ...but then compared with a log2(n) bound for edges

Neither base case is wrong on its own. The bug is mixing them: a node-counting height next to an edge-based formula, or a leaf check (if not node.left and not node.right: return 0) stacked on top of a None check that also returns 0. Pick a convention and say it in a comment.

Two-children delete that leaves a duplicate

succ = node.right
while succ.left is not None:
    succ = succ.left
node.value = succ.value      # copied, but the successor is still down there

node.right = self._delete(node.right, succ.value)

Copying the successor's value is only half the job; the old successor node must be removed from the right subtree, or its value appears twice. Removing it is easy because the successor never has a left child.

Cost of each operation

Operation	Average (h ≈ log n)	Worst (h = n − 1)	Why
Search	O(log n)	O(n)	one comparison per level, one path down
Insert	O(log n)	O(n)	search for the empty spot, then link a leaf
Delete	O(log n)	O(n)	find the node; the successor is further down the same kind of path
Min / max	O(log n)	O(n)	keep going left (min) or right (max)
Preorder / inorder / postorder	O(n)	O(n)	every node once; stack space O(h)
Height	O(n)	O(n)	every node once, postorder; stack space O(h)
Build from n values	O(n log n)	O(n²)	n inserts; sorted input is the worst case

Space for the tree itself is O(n): one Node per value. Recursive versions add O(h) for the call stack, which is O(log n) when balanced and O(n) when skewed.