Trees

Data Structures in Practice

Chapter 7 · Trees

A tree is a structure where each item (a node) points to zero or more children, and no node has more than one parent. Folders on a disk, the nesting of an HTML page and a company's reporting lines are all trees. A binary tree limits each node to at most two children, called left and right. Python has no built-in tree type, so you build one from small objects, just as in Data Structures in Practice 5, but with two pointers instead of one.

What was run, and what was not

Every snippet below was run and the output shown is what it printed. No timings are quoted, because they differ between machines. Heights and counts are exact, because they do not depend on the machine.

Nodes and Vocabulary

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

tree = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
    

That builds this shape, which the rest of the chapter reuses:

        8
       / \
      3   10
     / \    \
    1   6    14
    

Term	Meaning	In the picture
Root	The top node, with no parent	8
Leaf	A node with no children	1, 6, 14
Depth of a node	Steps from the root down to it	6 is at depth 2
Height of the tree	Number of levels (this chapter counts nodes on the longest path)	3
Subtree	A node together with everything below it	3, 1 and 6 form one

Walking a Tree: Four Orders

A list has one obvious way to visit every item. A tree has several. The three depth-first orders differ only in when the node itself is visited relative to its two subtrees, and the fourth goes level by level using a queue (Data Structures in Practice 4).

def inorder(n):      # left, node, right
    if n is None:
        return []
    return inorder(n.left) + [n.value] + inorder(n.right)

def preorder(n):     # node, left, right
    if n is None:
        return []
    return [n.value] + preorder(n.left) + preorder(n.right)

def postorder(n):    # left, right, node
    if n is None:
        return []
    return postorder(n.left) + postorder(n.right) + [n.value]

from collections import deque
def levelorder(n):   # top to bottom, left to right
    out, q = [], deque([n] if n else [])
    while q:
        cur = q.popleft()
        out.append(cur.value)
        if cur.left:  q.append(cur.left)
        if cur.right: q.append(cur.right)
    return out

print(inorder(tree))
print(preorder(tree))
print(postorder(tree))
print(levelorder(tree))
    

[1, 3, 6, 8, 10, 14]
[8, 3, 1, 6, 10, 14]
[1, 6, 3, 14, 10, 8]
[8, 3, 10, 1, 6, 14]
    

Each has a typical use. Pre-order copies a tree (parents before children). Post-order deletes or totals a tree (children before parents). Level order finds the nearest thing first. In-order is special for search trees, as the next section shows. The recursive versions above also build many temporary lists; for large trees you would use a generator, or the explicit-stack version in Exercise 3.

Binary Search Trees

A binary search tree (BST) adds one rule: for every node, everything in its left subtree is smaller and everything in its right subtree is larger. The tree above obeys it. That rule makes searching a series of left-or-right decisions, each throwing away a whole subtree, which is binary search (Data Structures in Practice 1) on a linked structure.

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, v):
        if self.root is None:
            self.root = Node(v); self.size += 1; return True
        cur = self.root
        while True:
            if v == cur.value:
                return False               # duplicates ignored
            side = "left" if v < cur.value else "right"
            nxt = getattr(cur, side)
            if nxt is None:
                setattr(cur, side, Node(v)); self.size += 1; return True
            cur = nxt

    def __contains__(self, v):
        cur = self.root
        while cur:
            if v == cur.value: return True
            cur = cur.left if v < cur.value else cur.right
        return False

b = BST()
for v in [8, 3, 10, 1, 6, 14, 6]:
    print(v, b.insert(v))
print(inorder(b.root), b.size)
print(6 in b, 7 in b)
    

True
True
True
True
True
True
False
[1, 3, 6, 8, 10, 14] 6
True False
    

Notice the in-order walk returned the values sorted. That is a direct consequence of the rule (everything smaller, then the node, then everything larger), and it is why a BST can give you sorted output and range queries without a separate sort. Insertion and lookup follow one path from the root to a leaf, so their cost is proportional to the height, not to the number of items.

Balance: The Whole Point

The cost being "proportional to the height" is only good news if the height stays small. A tree with n items can be as short as about log2(n) levels, or as tall as n. The shape depends on the insertion order.

import random

def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))

s = BST()
for v in range(1, 201):          # already sorted
    s.insert(v)
print(height(s.root))

vals = list(range(1, 201))
random.seed(1)
random.shuffle(vals)                  # same values, random order
r = BST()
for v in vals:
    r.insert(v)
print(height(r.root))
    

200
14
    

The same 200 values give a height of 200 when inserted in order (every new value goes right of the last, so the "tree" is a linked list) and 14 when shuffled (the exact figure varies with the shuffle, but stays close to the ideal of 8). Sorted input is the commonest real-world way to hit the bad case: data read from a sorted file or an auto-incrementing key.

Deep trees and recursion

Python limits recursion to about a thousand nested calls. A recursive height on a chain of 5,000 nodes (the sorted case) raised RecursionError when tried. Skewed trees therefore break recursive code as well as being slow. The iterative walks in Exercise 3 have no such limit.

There are two standard fixes. Self-balancing trees (AVL trees, red-black trees) rotate nodes during insertion to keep the height near log2(n); they are tricky to write, and rarely worth writing by hand. Or you can build the tree from sorted data deliberately, by taking the middle item as the root and recursing on each half, which is Exercise 1.

Do You Actually Need One in Python?

Mostly no. Python's built-in tools already cover what a BST offers, and they run as optimised C code rather than interpreted node-hopping.

You need	Reach for	Why
Membership or lookup by key	`set` / `dict`	Hashing is constant time (Data Structures in Practice 3)
Sorted data, search and range queries	A sorted list with `bisect`	Binary search with no node objects; inserting is linear, but fast in practice for moderate sizes
Only the smallest or largest, repeatedly	`heapq`	Data Structures in Practice 6
Hierarchical data (folders, menus, parsed documents, game moves)	A tree of your own nodes	The data really is a tree
Constant fast inserts and sorted order for millions of items	A balanced-tree library	Not in the standard library; this is where a real tree pays off

The practical rule

Trees earn their place when the data is naturally hierarchical. Using one purely as a sorted container is usually a sign to try a sorted list or a dict first.

Challenges

Exercise 1

Write from_sorted(items), which builds a balanced binary search tree from a sorted list by using the middle item as the root and recursing on each half (pass index bounds rather than slicing). Write height and inorder helpers and check sizes 0, 1, 7, 15 and 1000: print the size, the height and whether the in-order walk equals the input.

📄 View solution

Exercise 2

Write range_query(node, lo, hi), returning in order every value between lo and hi inclusive in a search tree, without visiting subtrees that cannot contain a match. Then write is_bst(node) that correctly rejects a tree in which every parent beats its direct children but a deeper node is on the wrong side. Build such a tree to prove it.

📄 View solution

Exercise 3

Write iterative generators inorder_iter and preorder_iter using an explicit stack, and levels returning a list of lists, one per level, using a deque. Check them on the chapter's example tree, on an empty tree, and on a right-leaning chain of 5,000 nodes that a recursive version could not handle.

📄 View solution

Quick Reference

Binary tree: each node has a value, a left child and a right child (either may be None)
Orders: in-order (left, node, right), pre-order (node first), post-order (node last), level order (queue)
BST rule: left subtree smaller, right subtree larger; in-order gives sorted output
Cost: insert and search follow one path, so cost is the height
Balance: shuffled input gives height near log2(n); sorted input gives height n
Validation: check each node against a window of allowed values, not only its parent
Deep trees: recursion hits Python's limit; use an explicit stack
In Python: prefer dict, set, bisect or heapq unless the data is truly hierarchical

Coming next

Data Structures in Practice 8 covers graphs: adjacency lists, breadth-first and depth-first search, and shortest paths on small graphs. A tree is a graph with no loops and one way in; next the loops are allowed.