DSA Tree Traversals, Recursively
A traversal is a walk that visits every node of a tree exactly once. Preorder, inorder and postorder are three traversals that differ only in when each node is visited.
Preorder: node, left, right
To visit a node means to use its value, here by adding it to a list. Preorder visits the node first, then walks its left subtree, then its right subtree.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(node, order):
if node is None:
return
order.append(node.value)
preorder(node.left, order)
preorder(node.right, order)
tree = TreeNode(2, TreeNode(1), TreeNode(3))
order = []
preorder(tree, order)
print("Preorder:", order)Inorder: left, node, right
Inorder walks the left subtree first. It visits the node between its two subtrees.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(node, order):
if node is None:
return
inorder(node.left, order)
order.append(node.value)
inorder(node.right, order)
tree = TreeNode(2, TreeNode(1), TreeNode(3))
order = []
inorder(tree, order)
print("Inorder:", order)Postorder: left, right, node
Postorder walks both subtrees first. It visits the node last of all.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def postorder(node, order):
if node is None:
return
postorder(node.left, order)
postorder(node.right, order)
order.append(node.value)
tree = TreeNode(2, TreeNode(1), TreeNode(3))
order = []
postorder(tree, order)
print("Postorder:", order)Example
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(node, order):
if node is None:
return
order.append(node.value)
preorder(node.left, order)
preorder(node.right, order)
def inorder(node, order):
if node is None:
return
inorder(node.left, order)
order.append(node.value)
inorder(node.right, order)
def postorder(node, order):
if node is None:
return
postorder(node.left, order)
postorder(node.right, order)
order.append(node.value)
def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
tree = TreeNode(4,
TreeNode(2, TreeNode(1), TreeNode(3)),
TreeNode(6, TreeNode(5), TreeNode(7)))
pre = []
preorder(tree, pre)
ino = []
inorder(tree, ino)
post = []
postorder(tree, post)
print("Preorder:", pre)
print("Inorder:", ino)
print("Postorder:", post)
print("Nodes in tree:", count_nodes(tree))
print("Visits in each walk:", len(pre), len(ino), len(post))Key points
- One recursive template makes all three orders, with only the visit line moved
- The base case is an empty child, and it adds nothing to the walk
- A traversal of n nodes visits n nodes, so the whole walk takes n steps
In this example, one tree with seven nodes is walked three times. Preorder starts at the root 4 and finishes each subtree before moving on. Inorder reaches 4 only after its whole left subtree, so the values come out in rising order for this tree. Postorder leaves 4 until the very end. Each list holds seven values, matching the node count, so every walk visited each node exactly once.
Note
The recursion follows the shape of the tree, so a very deep tree can reach Python's recursion limit
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
What is the postorder walk of a tree with root 5, left child 3 and right child 8?