Master

Trees & graphs

Organize data in hierarchical trees and connected graphs for nesting and networks.

What you will see

root A B E

About 2 min of reading

Try It

A tree organizes data hierarchically with one root and children branching down. I read a tree's root, count its nodes with recursion, and walk it depth-first to visit each name.

A tree has a single root and each node holds children. I print the root name and how many children it has, showing the top of the hierarchy.

tree = {"name": "root", "children": [{"name": "A", "children": []}, {"name": "B", "children": []}]} print(tree["name"]) print(len(tree["children"]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

root 2

A node with no children is a leaf. Children branch out below a parent; every node except the root has exactly one parent.

A recursive function counts a node as one, then adds the count of each child subtree, so the total reaches every node in the tree.

def count(node): total = 1 for child in node["children"]: total += count(child) return total tree = {"name": "root", "children": [ {"name": "A", "children": [{"name": "C", "children": []}]}, {"name": "B", "children": []}]} print(count(tree))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Recursion needs a base case, here a node with no children still returns 1, so every leaf stops the calls. Missing that base case loops forever.

Depth-first visits a node, then dives into its children before moving on. I walk the tree and print each name as I reach it.

def walk(node): print(node["name"]) for child in node["children"]: walk(child) tree = {"name": "root", "children": [ {"name": "A", "children": []}, {"name": "B", "children": [{"name": "E", "children": []}]}]} walk(tree)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

root A B E

The visit order depends on the order you recurse into children. A breadth-first walk would visit level by level instead.

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Nodes connect hierarchically; you traverse from the root, branching to children, or follow edges in a graph.

1 Start at the root or any node

↓

2 Visit children in a defined order

↓

3 Recurse or use a stack to go deeper

↓

4 Stop when every node is visited

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

tree = {"name": "root", "children": [{"name": "A", "children": []}, {"name": "B", "children": []}]} sets nothing on screen

print(tree["name"]) root

print(len(tree["children"])) 2

Why this works

Tree vocabulary

Key terms for trees:

**Root*: the top node.
**Parent / child*: a node points to the ones below it.
**Leaf*: a node with no children.
**Height*: how deep the tree goes.

        [root]   <- the only root
       /      \
  [parent]   [parent]
      /    \
   [leaf] [leaf]   <- no children

Knowing the words helps you talk about how trees work.

When you have a choice

Trees vs graphs

A graph is a general network of nodes and connections. A tree is a special graph with no loops and one root.

Tree:
   A
  / \
 B   C       (one path between any two nodes)

Graph:
   A---B
   |   |
   D---C    (you can loop around)

Graphs model maps, social networks, and how web pages link together. Trees are cleaner when data naturally nests.

Examples

A tree of nodes

One root, many branches

         [Root]
        /      \
     [A]        [B]
     / \          
   [C] [D]       [E]

A tree has one root and each node has at most one parent. Children branch out below. Files on a computer, and the DOM of a webpage, are trees.

Why it works: hierarchy lets you group related items under a common parent.

Binary search tree

Storing data so searching is fast

         [5]
        /   \
      [3]    [8]
      /          
    [2]       [10]

In a binary search tree, left children are smaller and right children are bigger. That lets you skip half the tree on each step when searching.

Look for 8? Skip the whole left side.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Linked lists

Previous Lesson

Linked lists

Next Lesson

Hash maps

Hash maps →