Tree Traversals
Depth first.
To print, search, or count a tree, you need to visit every node. Depth first traversal goes as deep as it can down one branch, before coming back to try the next. And recursion makes it beautifully short.

- Visit every node
- Go deep first
- Recursion makes it short
Three orders
There are three classic depth first orders, and they differ only in when we visit the node itself. Pre order visits the node first, then the left and right subtrees. In order visits left, then the node, then right. Post order visits both children first. Run it. Look at in order. For this kind of tree, it comes out sorted.
from tree import sample
def pre(n): return [n.value] + pre(n.left) + pre(n.right) if n else []
def ino(n): return ino(n.left) + [n.value] + ino(n.right) if n else []
def post(n): return post(n.left) + post(n.right) + [n.value] if n else []
root = sample()
print("pre: ", pre(root))
print("in: ", ino(root))
print("post:", post(root))pre: [8, 3, 1, 6, 4, 7, 10, 14, 13] in: [1, 3, 4, 6, 7, 8, 10, 13, 14] post: [1, 4, 7, 6, 3, 13, 14, 10, 8]
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'When to use each
Pre order is good for copying a tree, because you create each parent before its children. In order gives sorted order for binary search trees. And post order is good for deleting, or adding up sizes, because children are handled before their parent. All three are O of N.
| key | value |
|---|---|
| Pre order | copy a tree |
| In order | sorted output |
| Post order | children before parent |
| Cost | O(n) |
Summary
Pre order, in order, and post order differ only in when the node is visited. Each takes three lines of recursion. Next, visiting a tree level by level.
Key takeaways- Pre: node first
- In: node in the middle
- Post: node last