AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 14

Part 4 · Trees · Chapter 14

Trees and Binary Trees

A family tree, a filesystem, a table of contents, the DOM. Once you see the shape you see it everywhere — and four traversals are enough to visit any of them.

Reading

CLRS Ch. 10.4, 12

Focus

Hierarchy

Cost

O(h), h = height

Traversals

By the end of this chapter you can

Use tree vocabulary precisely: root, leaf, parent, depth, height, subtree
Implement the four traversals and say what each one is for
Explain why level-order needs a queue while the other three need a stack
Compute height, size and depth recursively, and relate height to search cost
Recognise the recursive shape of a tree problem and write the three-line solution

1The shape

Everything so far has been linear. A tree is the first structure where an element can have more than one successor, and that changes what is possible.

The table of contents

A book's contents page: parts contain chapters, chapters contain sections, sections contain subsections. Nothing contains itself, nothing has two parents, and there is exactly one path from the front of the book to any given subsection.

That is a tree. Not a metaphor for one — structurally the same object.

A tree is a set of nodes where:

One node is the root — the only node with no parent.
Every other node has exactly one parent.
There are no cycles. Following parents always reaches the root.

Drop the “exactly one parent” rule and you have a DAG. Drop “no cycles” and you have a graph — Chapter 19. Trees are the well-behaved middle ground, and that good behaviour is what makes the recursion in this chapter work.

Term	Means	In the contents-page analogy
Root	The node with no parent	The book itself
Leaf	A node with no children	A subsection with nothing under it
Parent / child	Directly above / below	Chapter and its sections
Subtree	A node plus everything below it	One chapter, entire
Depth of a node	Edges from the root down to it	How many levels indented
Height of a tree	Edges on the longest root-to-leaf path	The deepest nesting in the book
Level	All nodes at the same depth	All the chapters

Depth and height are not the same thing

Depth is measured downward from the root and belongs to a node. Height is measured upward from the deepest leaf and belongs to a node or the whole tree.

The root has depth 0. A leaf has height 0. A tree's height is its root's height. Mixing them up is the single most common source of off-by-one bugs in tree code, so it is worth pinning down now.

Trees are everywhere once you look:

Filesystems — directories contain files and directories.
The DOM — every web page is a tree of elements.
Expression trees — how a compiler represents 2 + 3 * 4.
Decision trees, syntax trees, org charts, JSON, XML, the call stack viewed over time.

2Binary trees

Restrict to at most two children and you get something small enough to reason about and general enough to build everything else on.

A binary tree allows each node at most two children, conventionally left and right. The restriction is what makes the code short: every recursive function has exactly two recursive calls.

binary_tree.py

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

#         4
#        / \
#       2   6
#      / \   \
#     1   3   7
tree = Node(4,
            Node(2, Node(1), Node(3)),
            Node(6, None, Node(7)))

Some shapes have names, and the names matter because they determine the height:

Kind	Definition	Height for n nodes
Full	Every node has 0 or 2 children	varies
Complete	Every level full except possibly the last, filled left to right	⌊log₂ n⌋
Perfect	Every level completely full	log₂(n+1) − 1
Balanced	Height is O(log n)	O(log n)
Degenerate	Every node has one child	n − 1 — a linked list

Complete is the important one for Chapter 17: a complete binary tree can be stored in a flat array with no pointers at all, because the shape is fully determined by the number of nodes. That is exactly what a heap does.

Height is the cost of everything

Almost every tree operation walks one root-to-leaf path, so it costs O(height).

A balanced tree of a million nodes has height 20. A degenerate one has height 999,999. Same node count, same code, and the difference between instant and unusable. Chapters 15 and 16 are entirely about keeping that number small.

3The four traversals

A traversal is a rule about when you read a node relative to visiting its children. Four rules, four completely different outputs.

Three of them are depth-first, differing only in where the read happens relative to the two recursive calls. That is the entire difference, and it is one line moved.

three_traversals.py

def preorder(node, out):
    if node is None: return
    out.append(node.value)      # ← read BEFORE both children
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if node is None: return
    inorder(node.left, out)
    out.append(node.value)      # ← read BETWEEN the two children
    inorder(node.right, out)

def postorder(node, out):
    if node is None: return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.value)      # ← read AFTER both children

The fourth is different in kind. Level-order visits all of depth 0, then all of depth 1, and so on. Recursion cannot express that naturally, because recursion goes deep. It needs a queue.

level_order.py

from collections import deque

def level_order(root):
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()          # popleft, not pop — that is the whole thing
        out.append(node.value)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

# Swap popleft() for pop() and you get a depth-first traversal instead.
# One method call decides the entire shape of the search. You will meet
# this again, with far larger consequences, in Chapter 20.

Traversal	Order	On a BST gives	Use it to
Pre-order	node, left, right	—	Copy or serialise a tree — parent written before children, so replay rebuilds it
In-order	left, node, right	sorted order	Read a BST out in order; verify it really is a BST
Post-order	left, right, node	—	Delete a tree; evaluate an expression tree; compute directory sizes
Level-order	by depth	—	Find the shallowest anything; print a tree by rows

Why in-order on a BST is sorted

The BST property says everything in the left subtree is smaller and everything in the right is larger. In-order visits all of the left, then the node, then all of the right — which is exactly “everything smaller, then me, then everything larger.”

So the sorted output is not a happy accident; it is the BST property read out loud. This also gives you the cleanest way to check a tree is a valid BST: do an in-order walk and confirm the output is increasing.

4Recursion on trees

Almost every tree function has the same three-line shape. Once you see it, most tree problems stop being problems.

A tree is defined recursively — a node plus two subtrees, each of which is a tree — so recursive functions on trees write themselves. The template:

the_template.py

def solve(node):
    if node is None:                 # 1. BASE CASE: the empty tree
        return <identity value>
    left  = solve(node.left)         # 2. solve both subtrees
    right = solve(node.right)
    return <combine node.value, left, right>    # 3. combine

Every function below is that template with a different combining step:

tree_recursion.py

def size(node):
    if node is None: return 0
    return 1 + size(node.left) + size(node.right)

def height(node):
    if node is None: return -1              # an empty tree has height -1,
    return 1 + max(height(node.left),       # so a LEAF has height 0
                   height(node.right))

def total(node):
    if node is None: return 0
    return node.value + total(node.left) + total(node.right)

def maximum(node):
    if node is None: return float("-inf")   # identity for max
    return max(node.value, maximum(node.left), maximum(node.right))

def count_leaves(node):
    if node is None: return 0
    if node.left is None and node.right is None: return 1
    return count_leaves(node.left) + count_leaves(node.right)

def mirror(node):
    """Flip the tree left-to-right, in place."""
    if node is None: return None
    node.left, node.right = mirror(node.right), mirror(node.left)
    return node

def is_same(a, b):
    if a is None and b is None: return True
    if a is None or b is None:  return False
    return (a.value == b.value
            and is_same(a.left,  b.left)
            and is_same(a.right, b.right))

Why height(None) is −1

It looks arbitrary and it is forced. If a leaf's height is 0 (no edges below it), then a leaf must satisfy 1 + max(h(None), h(None)) = 0, which requires h(None) = -1.

Define it as 0 instead and every height in your tree is off by one — and the bug will surface three chapters later, in a rotation. Getting the identity value right for the empty case is the whole trick to this template: 0 for counting, −∞ for maximum, −1 for height.

Cost

All of these visit every node exactly once, so they are O(n) time. Space is the recursion depth: O(h), which is O(log n) for a balanced tree and O(n) for a degenerate one.

Traversal

O(n)

Height / size

O(n)

Search (balanced BST)

O(log n)

Search (degenerate)

O(n)

Space (recursion)

O(h)

5Building and printing trees

Two practical skills: turning a flat description into a tree, and getting a tree onto the screen so you can see what you built.

From a level-order list

The standard interchange format — the one every online judge uses — is a level-order list with None for missing children.

build.py

from collections import deque

def build(values):
    """[4,2,6,1,3,None,7] → the tree, level by level."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i]); q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i]); q.append(node.right)
        i += 1
    return root

Printing a tree sideways

The easiest readable tree printer rotates the picture 90°: a reverse in-order walk, indented by depth. The root ends up on the left margin and the tree reads top to bottom.

show.py

def show(node, depth=0):
    if node is None:
        return
    show(node.right, depth + 1)          # right subtree ABOVE
    print("    " * depth + str(node.value))
    show(node.left, depth + 1)           # left subtree BELOW

#         7
#     6
#         (nothing)
# 4
#         3
#     2
#         1
#
# Read it with your head tilted left. Twelve lines of code, and it will
# save you an hour every time a tree is not the shape you expected.

Serialisation, and why pre-order

To save a tree and rebuild it later, use pre-order with explicit markers for missing children:

4 2 1 # # 3 # # 6 # 7 # #

Pre-order works because the parent is written before its children, so a single left-to-right replay can rebuild the tree without look-ahead. In-order alone is not enough — many different trees share an in-order sequence, which is exactly why a BST's in-order output loses the shape.

What to carry forward

A tree is nodes with one root, one parent each, and no cycles. Relax those rules and you get DAGs and graphs.
Depth counts down from the root; height counts up from the leaves. Root depth 0, leaf height 0, empty tree height −1.
Height is the cost of everything. Balanced means O(log n); degenerate means O(n) — same code, same node count.
Pre-, in- and post-order differ by one line moved: read before, between, or after the two recursive calls.
Level-order needs a queue, not recursion. Swapping the queue for a stack turns it into depth-first — remember that for Chapter 20.
Most tree functions are the same template: base case for None, recurse both sides, combine. Getting the empty-case identity right is the whole trick.

>_Playground

Build a tree, walk it four ways, and print it sideways. Change the values and see the traversals change.

scratch.pypython not loaded

from collections import deque

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

def build(values):
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    q, i = deque([root]), 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i]); q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i]); q.append(node.right)
        i += 1
    return root

def preorder(n, out=None):
    out = [] if out is None else out
    if n: out.append(n.value); preorder(n.left, out); preorder(n.right, out)
    return out

def inorder(n, out=None):
    out = [] if out is None else out
    if n: inorder(n.left, out); out.append(n.value); inorder(n.right, out)
    return out

def postorder(n, out=None):
    out = [] if out is None else out
    if n: postorder(n.left, out); postorder(n.right, out); out.append(n.value)
    return out

def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        n = q.popleft()
        out.append(n.value)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out

def show(n, depth=0):
    if n is None: return
    show(n.right, depth + 1)
    print("    " * depth + str(n.value))
    show(n.left, depth + 1)

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

def size(n):
    return 0 if n is None else 1 + size(n.left) + size(n.right)

t = build([4, 2, 6, 1, 3, None, 7])

print("the tree, rotated 90 degrees (tilt your head left):")
show(t)
print()
print("pre-order  :", preorder(t),   " <- parent first: use to COPY a tree")
print("in-order   :", inorder(t),    " <- sorted, because this happens to be a BST")
print("post-order :", postorder(t),  " <- children first: use to DELETE a tree")
print("level-order:", level_order(t)," <- by depth, needs a queue")
print()
print("size   :", size(t))
print("height :", height(t), "  (a leaf has height 0; an empty tree has -1)")
print()

# What happens to the height when the tree degenerates?
degenerate = build([1, None, 2])
degenerate.right.right = Node(3)
degenerate.right.right.right = Node(4)
print("degenerate tree of 4 nodes has height", height(degenerate), "- it is a linked list")

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 15 — Binary Search Trees

A binary search that lives in the structure itself. Beautiful when balanced, and quietly catastrophic when you insert sorted data.

Continue →