Preorder, Inorder and Postorder Traversals
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A traversal visits every node once. The three depth-first orders differ only in when the node is handled. This lesson writes each one with recursion, then with an explicit stack for very deep trees.
Preorder: node, left, right
Tree traversal is a way to visit every node of a tree exactly once in a fixed order. The three depth-first orders differ in when the node itself is handled: before, between or after its two subtrees.
To process every node you need a fixed visiting order. Preorder handles a node first, then its whole left subtree, then its whole right subtree. A function that calls itself on each child does it.
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def preorder(node): if node: yield node.val yield from preorder(node.left) yield from preorder(node.right)print(list(preorder(root)))Example 1 · Watch the recursion
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def walk(node, depth=0): if node is None: return print(" " * depth + "enter", node.val) walk(node.left, depth + 1) walk(node.right, depth + 1) print(" " * depth + "leave", node.val)
walk(TreeNode(1, TreeNode(2), TreeNode(3)))enter 1 enter 2 leave 2 enter 3 leave 3 leave 1
What this code does
- A call enters a node, finishes both subtrees and then leaves. Preorder work goes before the two calls, inorder work between them and postorder work after them.
- The indent shows how deep the call stack is.
if node: is the base case: a missing child does nothing. yield from hands on every value the call below produces. Each node is visited once, so time is O(n).
Inorder: left, node, right
Inorder finishes the left subtree before it handles the node. In a binary search tree, where smaller values sit on the left, this visits the values in sorted order.
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightroot = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))def inorder(node): if node: yield from inorder(node.left) yield node.val yield from inorder(node.right)print(list(inorder(root)))Example 2 · Inorder of a search tree is sorted
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def insert(node, val): if node is None: return TreeNode(val) if val < node.val: node.left = insert(node.left, val) else: node.right = insert(node.right, val) return node
def inorder(node): return inorder(node.left) + [node.val] + inorder(node.right) if node else []
root = Nonefor price in [50, 30, 70, 20, 40, 60]: root = insert(root, price)print(inorder(root))[20, 30, 40, 50, 60, 70]
What this code does
- Smaller prices go left and larger ones go right. Inorder then reads them in increasing order.
- This version joins lists, which is simple but copies values. The generator version avoids that.
The tree has 1 and 3 under 2, and 2 and 6 under 4. Left, node, right gives 1 2 3 4 6, which is sorted.
Postorder: left, right, node
Postorder handles both subtrees first and the node last. Use it when a node needs the answers of its children, such as the total size of a folder or deleting a tree.
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def postorder(node): if node: yield from postorder(node.left) yield from postorder(node.right) yield node.valprint(list(postorder(root)))Example 3 · Folder sizes with postorder
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def total(node): if node is None: return 0 size = node.val + total(node.left) + total(node.right) print("folder", node.val, "holds", size) return size
root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(1)), TreeNode(4))total(root)folder 2 holds 2 folder 1 holds 1 folder 3 holds 6 folder 4 holds 4 folder 5 holds 15
What this code does
- A folder can only report its size after its subfolders have reported theirs, so the print comes after the two calls.
- The children are printed before their parent, which is postorder.
Node 1 is last, because everything below it comes first. Preorder, inorder and postorder all run in O(n) time and use stack space equal to the height of the tree.
Without recursion: a stack
Recursion uses the call stack. You can keep your own stack of nodes instead. For preorder, take a node, record it, then push the right child first so the left child is taken next.
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def preorder(root): result, stack = [], [root] while stack: node = stack.pop() if node: result.append(node.val) stack += [node.right, node.left] return resultprint(preorder(root))Example 4 · Recursive and iterative agree
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def pre_rec(node): return [node.val] + pre_rec(node.left) + pre_rec(node.right) if node else []
def pre_iter(root): result, stack = [], [root] while stack: node = stack.pop() if node: result.append(node.val) stack += [node.right, node.left] return result
print(pre_rec(root) == pre_iter(root))True
What this code does
- Both give 1 2 4 5 3 6. The stack takes the place of the call stack.
- Push right before left: the last item pushed is the first one taken.
A list works as a stack: append pushes and pop() takes the last item. This version cannot hit the recursion limit on a very deep tree.
Inorder with a stack
Inorder is harder without recursion. Walk left as far as possible and push every node on the way. Then pop one, record it and move to its right child.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def inorder(root): result, stack, node = [], [], root while stack or node: while node: stack.append(node) node = node.left node = stack.pop() result.append(node.val) node = node.right return resultprint(inorder(root))Example 5 · Postorder with two stacks of work
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def postorder(root): result, stack = [], [root] while stack: node = stack.pop() if node: result.append(node.val) stack += [node.left, node.right] return result[::-1]
print(postorder(root))[4, 5, 2, 6, 3, 1]
What this code does
- Visit node, right, left, and then reverse the list. Reversed, this reads left, right, node, which is postorder.
- It is a short trick for iterative postorder. A real two-state stack is longer to write.
Example 6 · One order is not enough
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
a = TreeNode(1, TreeNode(2))b = TreeNode(1, None, TreeNode(2))
def pre(node): return [node.val] + pre(node.left) + pre(node.right) if node else []
def ino(node): return ino(node.left) + [node.val] + ino(node.right) if node else []
print(pre(a), pre(b))print(ino(a), ino(b))[1, 2] [1, 2] [2, 1] [1, 2]
What this code does
- Two different trees can share the same preorder. Adding the inorder tells them apart.
- This is why building a tree from traversals, in the last lesson, uses two of them.
The stack holds the nodes whose left side is being processed, so it never grows beyond the height of the tree plus one.
Next step
Check your understanding
12 quick questions