Card 02/ 08
Traverse a Binary Tree in Pre-, In- and Post-Order
The three orders differ only in when a node is visited relative to its two subtrees.
A traversal of a tree visits every node exactly once, in an order fixed by a rule. This card covers the three depth-first orders of a binary tree, pre-order, in-order and post-order, and a procedure for writing each one down by hand. Depth-first means that each order finishes a whole subtree, a node and everything below it, before it moves on.
All three come from one recursive function. At each node there are three jobs: visit the node, which here means appending its value to a list; traverse its left subtree; and traverse its right subtree. The left subtree always comes before the right. The only difference is where the visit goes. Pre-order visits a node before both its subtrees, in-order between them, and post-order after both.
The tree used throughout this topic has the root 1 with children 2 and 3. Node 2 has children 4 and 5, node 3 has only a right child, 6, and node 6 has only a left child, 7.
Before the procedure: what is the in-order sequence of this tree?
4 2 5 1 3 7 6. In-order finishes the whole left subtree of 1, giving 4 2 5, before it visits 1, and only then traverses the right subtree, giving 3 7 6. Node 3 has no left child, so it is visited as soon as it is reached, and 7 comes before 6 because 7 is 6's left child.
To trace an order by hand, apply the rule at each node and keep a note of the node to return to. For in-order at the root 1, the left subtree comes first, so go to 2, and before 2, to its left subtree, the leaf 4. A leaf's subtrees are empty, so 4 is visited at once. Back at 2, visit 2, then traverse its right subtree, 5. The left subtree of 1 is now finished, so visit 1, then move to 3 and apply the same rule there.
The listing is the one function with the visit line in three places, highlighted, and it was run on this tree in all three orders:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def walk(node, order, visited):
if node is None:
return
if order == "pre":
visited.append(node.value)
walk(node.left, order, visited)
if order == "in":
visited.append(node.value)
walk(node.right, order, visited)
if order == "post":
visited.append(node.value)
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6, Node(7))))
for order in ("pre", "in", "post"):
visited = []
walk(root, order, visited)
print(f"{order}-order:", *visited)pre-order: 1 2 4 5 3 6 7
in-order: 4 2 5 1 3 7 6
post-order: 4 5 2 7 6 3 1A quicker check works on the drawing. Trace a line around the outline of the tree, starting to the left of the root, down the left side and back up the right. The line passes every node three times: on its left, beneath it, and on its right. Pre-order lists each node as the line passes its left side, in-order as it passes beneath, and post-order as it passes its right side. The tree gives every node's position in each order, as the listing printed them.
1, pre 1st, in 4th, post 7th
2, pre 2nd, in 2nd, post 3rd
4, pre 3rd, in 1st, post 1st
5, pre 4th, in 3rd, post 2nd
3, pre 5th, in 5th, post 6th
null
6, pre 6th, in 7th, post 5th
7, pre 7th, in 6th, post 4th
Each order has its typical uses, because each decides what is already known when a node is visited. Pre-order visits a parent before its children, so it suits copying a tree or printing it as an indented outline. Post-order visits a node after both its subtrees, so it suits work that needs the children's results first, such as deleting a tree or adding up the sizes of folders. In-order visits the left subtree, then the node, then the right. In a binary search tree, a binary tree that keeps smaller values to the left of a node and larger ones to the right, in-order gives the values in sorted order. Each order visits every node once, so each takes O(n) time on a tree of n nodes.
← → move through sections and cards