Vocabulary

A linked list joins each node to one next node. A tree lets a node lead to several nodes. Trees hold anything with a top-down shape: folders on a disk, the parts of a web page, the moves of a game. This lesson gives the words used for trees, and the main tool for working with them: recursion.

Root, children, leaves

Step through the figure. Each step names one part of the tree.

The words, in one place:

• Node and edge: the boxes, and the lines joining a node to a node below it.
• Root: the one node with nothing above it. Parent and child: the two ends of an edge, upper and lower. Leaf: a node with no children.
• Depth of a node: the number of edges from the root down to it. Level: all the nodes with the same depth.
• Height of the tree: the largest depth of any node. A tree with one node has height 0. An empty tree has height −1 by convention, which makes the formulas below work.
• Subtree of a node: that node and everything below it. Ancestors of a node: the nodes on its path up to the root. Descendants: the nodes in its subtree.

Binary trees in Python

In a binary tree, each node has at most two children, called left and right. Left and right are different places: a node with only a left child is a different tree from a node with only a right child. In Python, a node is a small object, like a linked-list node with two references instead of one:

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left          # the left child, or None
        self.right = right        # the right child, or None

root = TreeNode(8, TreeNode(3), TreeNode(10))

The tree as a whole is a reference to its root; an empty tree is None. The practice problems write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. [8, 3, 10, None, 6] is 8 with children 3 and 10, where 3 has only a right child, 6.

Height and the number of nodes

Level d of a binary tree holds at most 2^d nodes (d twos multiplied together; 2⁰ is 1): 1 root, at most 2 children, at most 4 grandchildren, and so on, doubling at each level. So a tree of height h has at most 1 + 2 + 4 + … + 2^h = 2^h+1 − 1 nodes. A tree with every level completely full is called perfect.

Turn this around. A tree with n nodes has height at least log₂ n rounded down. (Recall that log₂ n is the number of times you can halve n before reaching 1.) At the other end, a tree where every node has one child is a path, with height n − 1.

Much of this station and the next one is about that gap. Many tree jobs walk one path from the root, so they cost O(h). That is O(log n) for a short, bushy tree, and O(n) for a path.

Two more shape words appear often. A full binary tree is one where every node has 0 or 2 children. A complete binary tree has every level full except possibly the last, which is filled from the left. Heaps (HEAP station) are complete trees.

Thinking recursively

A subtree is itself a tree. So a question about a tree can often be answered from the same question about its two subtrees. The empty tree is the base case. The second variant of the figure computes the height this way. Here are three such functions:

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
    return 1 + max(height(node.left), height(node.right))

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

Each function calls itself once for each child, so every node is visited once: O(n) time. The calls waiting at any moment form a path from the root, so the recursion goes h + 1 calls deep (RECR-2). That is the hidden cost of recursion on trees.