Python Program for Inorder, Preorder and Postorder Traversal
Intermediate Data structures Time O(n) Space O(n)
Visits every node of a small binary tree in in-order, pre-order and post-order with three short recursive functions.
A binary tree is made of nodes, each with a value and up to two children, a left and a right. To traverse it is to visit every node once, and there are three classic orders, named after when a node comes compared with its two subtrees:
- In-order (inorder): the left subtree, then the node, then the right subtree.
- Pre-order (preorder): the node first, then its left and right subtrees.
- Post-order (postorder): the left and right subtrees first, then the node.
For the tree drawn in the program, with 1 at the top, in-order gives 4, 2, 5, 1, 3. Each order has its uses: in-order lists a binary search tree's values sorted, pre-order copies a tree (parents before their children), and post-order deletes one or adds up folder sizes (children before their parents).
Program
class Node:
"""A value with a left and a right child."""
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def in_order(node, values):
"""Left subtree, then the node, then the right."""
if node:
in_order(node.left, values)
values.append(node.value)
in_order(node.right, values)
return values
def pre_order(node, values):
"""The node, then its left subtree, then its right."""
if node:
values.append(node.value)
pre_order(node.left, values)
pre_order(node.right, values)
return values
def post_order(node, values):
"""Left subtree, then the right, then the node."""
if node:
post_order(node.left, values)
post_order(node.right, values)
values.append(node.value)
return values
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print("In-order:", in_order(root, []))
print("Pre-order:", pre_order(root, []))
print("Post-order:", post_order(root, []))
Open in the editor Download binary_tree_traversals.py
Output
In-order: [4, 2, 5, 1, 3]
Pre-order: [1, 2, 4, 5, 3]
Post-order: [4, 5, 2, 3, 1]
How it works
Step through the program line by line: each step below shows up as its line runs.
- A
Nodeholds a value and its left and right children. A child that isn't given isNone, soNode(4)is a leaf, a node with no children. -
in_order()does nothing for an empty subtree (None), and that is what ends the recursion. For a node, it visits the whole left subtree, adds the node's value to the listvalues, then visits the right subtree. It returnsvaluesso the caller can print it. -
pre_order()is the same three lines in a different order: the value goes in first, before either subtree. -
post_order()adds the value last, after both subtrees. - The program builds the tree drawn above it, from the leaves up:
Node(2, Node(4), Node(5))is the node 2 with the children 4 and 5. - It prints each order, giving each function a new empty list to fill.
The in-order walk of this tree, call by call:
| Call on | What it does | values afterwards |
|---|---|---|
| 1 | Goes left to 2 first | [] |
| 2 | Goes left to 4 first | [] |
| 4 | No left child; adds 4; no right child | [4] |
| 2 | Back from 4: adds 2, then goes right to 5 | [4, 2] |
| 5 | No children; adds 5 | [4, 2, 5] |
| 1 | Back from 2: adds 1, then goes right to 3 | [4, 2, 5, 1] |
| 3 | No children; adds 3 | [4, 2, 5, 1, 3] |
The only difference between the three functions is where values.append(node.value) sits: before the two calls,
between them, or after them.
Time and space complexity
| Time | O(n) |
|---|---|
| Extra space | O(n) |
Each function is called once for every node and once for every missing child (None), and a tree of n nodes has
n + 1 missing children, so each traversal takes O(n) time. The list of values grows to n items, and the calls waiting
on each other go as deep as the tree is tall, its height h. That's about log₂ n levels for a balanced tree but n for
a tree that is a single chain, so the extra space is O(n) in the worst case.
Other ways to write it
In-order without recursion
A stack of the nodes still waiting does the job of the recursive calls: go left as far as possible, pushing each node on the way, then pop one, take its value and go to its right.
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def in_order(root):
values, stack, node = [], [], root
while stack or node:
if node:
stack.append(node) # come back to it after its left side
node = node.left
else:
node = stack.pop()
values.append(node.value)
node = node.right
return values
print(in_order(Node(1, Node(2, Node(4), Node(5)), Node(3))))Level order, with a queue
Level order (breadth-first) visits the tree row by row, from the top. It uses a queue instead of recursion: take the node at the front, then add its children at the back.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def level_order(root):
values, queue = [], deque([root])
while queue:
node = queue.popleft()
if node:
values.append(node.value)
queue.append(node.left)
queue.append(node.right)
return values
print(level_order(Node(1, Node(2, Node(4), Node(5)), Node(3))))Try it yourself
- Give 3 a left child,
Node(3, Node(6)), and work out the three orders before you run it. - Build the tree for
2 + 3 * 4:Node("+", Node(2), Node("*", Node(3), Node(4))). In-order gives the sum as written, pre-order gives+ 2 * 3 4and post-order gives2 3 4 * +. - Write
count(node), which returns how many nodes a tree has, in the same shape: 0 forNone, otherwise 1 plus the counts of both subtrees. - Write
height(node), which returns how many levels a tree has: 3 for this one.