DailyRNG
Login
Advanced

Tree traversal

A tree is a node with subtrees, so recursion is the natural way to visit it. Pre-order, in-order, and post-order are the same walk with the visit moved.

What you will see

6

About 3 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Walk a tree with recursion.

1

Size of a tree.

def size(node): if node is None: return 0 return 1 + size(node.get("left")) + size(node.get("right")) tree = {"v": 1, "left": {"v": 2}, "right": {"v": 3}} print(size(tree))

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

What it prints
3
2

In-order list.

def inorder(node): if node is None: return [] return inorder(node.get("left")) + [node["v"]] + inorder(node.get("right")) tree = {"v": 2, "left": {"v": 1}, "right": {"v": 3}} print(inorder(tree))

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

What it prints
[1, 2, 3]
3

Height of a tree.

def height(node): if node is None: return 0 return 1 + max(height(node.get("left")), height(node.get("right"))) tree = {"v": 1, "left": {"v": 2, "left": {"v": 3}}} print(height(tree))

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

What it prints
3
4

Sum tree values.

def total(node): if node is None: return 0 return node["v"] + total(node.get("left")) + total(node.get("right")) tree = {"v": 1, "left": {"v": 2}, "right": {"v": 3}} print(total(tree))

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

What it prints
6

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

A tree is a node with subtrees, so recursion visits it naturally. Pre, in, and post order are the same walk with the visit moved.
1 visit node
↓
2 recurse left child
↓
3 recurse right child
↓
4 None is base
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.

def size(node): sets nothing on screen
if node is None: sets nothing on screen
return 0 sets nothing on screen
return 1 + size(node.get("left")) + size(node.get("right")) sets nothing on screen
tree = {"v": 1, "left": {"v": 2}, "right": {"v": 3}} sets nothing on screen
print(size(tree)) 3
Why this works
Order is where you visit

The three orders are one recursion with the node visit placed before, between, or after the child calls. Pick the one the task needs.

None is the base

A missing child is None and returns the empty answer. Every branch of a tree walk ends there.

Examples

Node with children

def size(node):
    if node is None:
        return 0
    return 1 + size(node.get("left")) + size(node.get("right"))
tree = {"v": 1, "left": {"v": 2}, "right": {"v": 3}}
print(size(tree))

A node is counted, then each child subtree. None is the base case for a missing child.

In-order gives sorted

def inorder(node):
    if node is None:
        return []
    return inorder(node.get("left")) + [node["v"]] + inorder(node.get("right"))
tree = {"v": 2, "left": {"v": 1}, "right": {"v": 3}}
print(inorder(tree))

Left, then node, then right. On a search tree that order is sorted.

Pre-order visits first

def preorder(node):
    if node is None:
        return []
    return [node["v"]] + preorder(node.get("left")) + preorder(node.get("right"))
tree = {"v": 2, "left": {"v": 1}, "right": {"v": 3}}
print(preorder(tree))

Node before children. That order copies the shape top down.

Post-order visits last

def postorder(node):
    if node is None:
        return []
    return postorder(node.get("left")) + postorder(node.get("right")) + [node["v"]]
tree = {"v": 2, "left": {"v": 1}, "right": {"v": 3}}
print(postorder(tree))

Children before node. Useful when a parent needs its children solved first.

Depth of a tree

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.get("left")), height(node.get("right")))
tree = {"v": 1, "left": {"v": 2, "left": {"v": 3}}}
print(height(tree))

The taller branch plus one. None has height zero, the base.

Sum the values

def total(node):
    if node is None:
        return 0
    return node["v"] + total(node.get("left")) + total(node.get("right"))
tree = {"v": 1, "left": {"v": 2}, "right": {"v": 3}}
print(total(tree))

Node value plus both subtrees. The same recursion shape as size.

A leaf is the base

def size(node):
    if node is None:
        return 0
    return 1 + size(node.get("left")) + size(node.get("right"))
tree = {"v": 9}
print(size(tree))

A leaf has two None children, each returning zero. The leaf itself counts one.

Search tree in-order

def inorder(node):
    if node is None:
        return []
    return inorder(node.get("left")) + [node["v"]] + inorder(node.get("right"))
tree = {"v": 3, "left": {"v": 1, "left": {"v": 2}}, "right": {"v": 4}}
print(inorder(tree))

In-order on a search tree lists values in order. The walk respects the ordering.

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.

← Divide and conquer
Previous Lesson
Divide and conquer
Next Lesson
Backtracking
Backtracking →