Binary trees

Introduction

A binary tree is like a linked list where each node can point to two others: a left child and a right child. The top node is the root, and nodes with no children are leaves. Trees are everywhere: file systems, decision trees, database indexes.

Trees appear wherever things contain other things: folders, web pages, organisation charts, the structure of a program. Most tree problems share one shape, which is why recursion fits them so well.

How it works

Visiting every node

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

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

root = Tree(5, Tree(3, Tree(1)), Tree(8))
print(inorder(root))

The tree here is 5 at the root, 3 on its left (with 1 below it), and 8 on its right. Tree problems are naturally recursive: "the answer for this node" is built from "the answers for its children". An in-order visit returns the left subtree, then the node, then the right subtree, which gives [1, 3, 5, 8]. Watch the call stack grow as the recursion goes down the left side.

A binary search tree

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

def insert(node, value):
    if node is None:
        return Tree(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)
print(root.value, root.left.value, root.right.value, root.left.left.value)

In a binary search tree (BST), smaller values go left and larger values go right. Inserting 5, 3, 8, 1 places 5 at the root, 3 to its left, 8 to its right, and 1 to the left of 3. Searching then needs only one path from the root down, about O(log n) steps when the tree is balanced, just like binary search.

Syntax

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

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

Example

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

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

root = Tree(5, Tree(3, Tree(1)), Tree(8))
print(height(root))

The height of an empty tree is 0; otherwise it is 1 plus the taller of the two subtrees. Here the longest path, 5 → 3 → 1, has 3 nodes.

Line by line

1. root is built with 5 at the top, 3 and 8 below it, and 1 below 3.
2. height(root) needs the heights of both children.
3. A missing child returns 0, which is the base case.
4. Each node adds 1 to the taller of its two sides.
5. The longest path has 3 nodes, so the result is 3.

Expected result

3

In the real world

Database indexes use tree structures to find rows quickly. The HTML of every web page is a tree, and compilers turn source code into a tree before doing anything else with it.

Common mistakes

• Forgetting the None base case, which raises AttributeError when the recursion reaches a missing child.
• Not storing the result of insert: node.left = insert(node.left, value) is needed, or new nodes are lost.
• Inserting already sorted values into a BST, which makes a long chain (O(n) height) instead of a bushy tree.

Best practices

• Write the None case first.
• Let a function ask only about one node and its children.
• Store the result when you rebuild links, as in node.left = insert(...).

Summary

A binary tree is made of nodes with up to two children. Recursion solves most tree problems by combining the answers for the two subtrees. A binary search tree keeps smaller values to the left, which makes searching fast.

Practice

Write count_leaves(node) that returns how many nodes have no children, and test it on the tree from the first example (the answer is 2).

Mark lesson complete