Trees & Binary Trees

Move from linear structures to hierarchical ones, and learn the traversal orders every tree algorithm builds on

Introduction

Arrays, linked lists, stacks, and queues have all been fundamentally linear: one element leads to the next. Hash tables loosened that by letting you jump straight to a value through its key, but the storage underneath was still one flat array of buckets. A tree breaks the mold entirely. It's a hierarchical structure where each element can branch into several others, exactly like a file system's folders, an HTML document's DOM, or an org chart. A binary tree, where every node has at most two children, is the simplest and most common variant, and it's the foundation the rest of this course builds on: binary search trees, heaps, and much of graph theory all start here.

Tree Terminology

In general, a tree lets any node have any number of children, a file system folder can contain any number of files and subfolders, an HTML element can have any number of child elements, an org chart's manager can have any number of direct reports. The vocabulary below (root, parent, child, leaf, depth, height, subtree) applies to every tree, general or binary.

A binary tree is the special case where every node has at most two children, conventionally called left and right. That restriction is what the rest of this lesson, and most of the tree structures later in this course, focus on, since it keeps the code simple while still capturing everything hierarchical structures are good for:

A Small Binary Tree

1root23leaf4leaf5leaf

Figure 1: Node 1 is the root, nodes 3, 4, and 5 are leaves

TermMeaning
RootThe single top-level node with no parent (node 1 above)
Parent / Child1 is the parent of 2 and 3; 2 and 3 are its children
LeafA node with no children (3, 4, and 5)
Depth of a nodeNumber of edges from the root down to that node
Height of a treeThe depth of its deepest leaf
SubtreeAny node together with all of its descendants, itself a valid tree

Binary Trees and the Node Class

A binary tree node looks a lot like Lesson 3's linked list node, except instead of one next pointer, it has two: left and right.

class TreeNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "TreeNode | None" = None
        self.right: "TreeNode | None" = None
#        1
#       / \
#      2   3
#     / \
#    4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

Depth-First Traversals

"Visiting every node" isn't a single operation, the order you visit them in matters, and different orders serve different purposes. Depth-first traversals go as deep as possible down one branch before backtracking, and they map almost directly onto Lesson 5's recursion: the base case is an empty subtree, the recursive case processes the two children.

PreorderRoot, then left, then right
InorderLeft, then root, then right
PostorderLeft, then right, then root
def preorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    # Root first, then everything on the left, then everything on the right
    return [node.value] + preorder(node.left) + preorder(node.right)
def inorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    # Left first, then the root, then the right
    return inorder(node.left) + [node.value] + inorder(node.right)
def postorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    # Both children before the root itself
    return postorder(node.left) + postorder(node.right) + [node.value]
print(preorder(root))
print(inorder(root))
print(postorder(root))
Expected Output:
[1, 2, 4, 5, 3]
[4, 2, 5, 1, 3]
[4, 5, 2, 3, 1]

The small number under each node is the order that traversal actually visits it. Same tree, same recursive shape every time, only the moment the root is recorded moves, and that alone produces three different sequences:

Preorder (Root, L, R)

11st22nd35th43rd54th

Visit order: 1 → 2 → 4 → 5 → 3

Inorder (L, Root, R)

14th22nd35th41st53rd

Visit order: 4 → 2 → 5 → 1 → 3

Postorder (L, R, Root)

15th23rd34th41st52nd

Visit order: 4 → 5 → 2 → 3 → 1

Only the Position of the Root Changes

Compare the three functions: the recursive structure is identical, only where node.value gets inserted relative to the two recursive calls changes. This is a pattern you'll see again and again in tree algorithms.

Breadth-First Traversal (Level Order)

Instead of diving deep, a level order traversal visits every node on one level before moving to the next. That requires remembering which nodes are "next in line", exactly the FIFO behavior a queue provides, so Lesson 4's deque does the work here instead of the call stack.

from collections import deque

def level_order(root: "TreeNode | None") -> list[int]:
    if root is None:
        return []

    result: list[int] = []
    queue: deque[TreeNode] = deque([root])   # Lesson 4's queue, not a stack

    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

    return result
print(level_order(root))
Expected Output:
[1, 2, 3, 4, 5]

Each node is enqueued once and dequeued once, so level order traversal is O(n), the same as every DFS order, just with a different data structure driving it and a different visiting order.

Recursive Tree Algorithms

Most questions about a tree, how tall is it, how many nodes does it have, is it balanced, have the same shape: solve the trivial case for an empty tree, then combine the answers from the left and right subtrees.

def height(node: "TreeNode | None") -> int:
    if node is None:
        return -1   # convention: an empty tree has height -1
    return 1 + max(height(node.left), height(node.right))

def count_nodes(node: "TreeNode | None") -> int:
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)
print(height(root))
print(count_nodes(root))
Expected Output:
2
5

height answers "how many edges to the deepest leaf", count_nodes answers "how many nodes total". Both visit every node exactly once, O(n), and both are only a few lines because the recursion does the traversal for free.

Bonus: Inverting a Binary Tree

Famously the subject of a viral interview-question controversy, inverting a tree means mirroring it: every node's left and right children are swapped, all the way down.

def invert(node: "TreeNode | None") -> "TreeNode | None":
    if node is None:
        return None
    # Swap the children, then invert each of the (now swapped) subtrees
    node.left, node.right = invert(node.right), invert(node.left)
    return node
print(preorder(root))
invert(root)
print(preorder(root))
Expected Output:
[1, 2, 4, 5, 3]
[1, 3, 2, 5, 4]

Notice the swap happens on the way down the recursion, each node hands its (already-inverted) subtrees to its parent, which just needs to place them on the opposite sides. Like the traversals above, it's O(n): every node is visited, and swapped, exactly once.

Key Takeaways

  • Trees are hierarchical, not linear - each node can branch into multiple children instead of pointing to a single next element
  • Preorder, inorder, and postorder are the same recursive DFS shape, they only differ in where the root is visited relative to its children
  • Level order traversal needs a queue, not the call stack, to visit nodes breadth-first instead of depth-first
  • Every full traversal is O(n) - each node is visited exactly once, regardless of which order you choose
  • Recursive tree algorithms follow one template: handle the empty case, then combine the results from the left and right subtrees
Data Structures & AlgorithmsLesson 7