Tree traversals

The idea

The orders differ only in when a node is written down

A traversal visits every node of a tree exactly once. A list has one natural order, front to back. A binary tree has several, and the common ones each have a name. Three of them come from one recursive function: handle the left subtree, handle the right subtree, and write the node itself at one of three moments.

Order	The node is written	On the tree 4 (2 (1, 3), 6)
Preorder	before its subtrees: node, left, right	4, 2, 1, 3, 6
Inorder	between them: left, node, right	1, 2, 3, 4, 6
Postorder	after them: left, right, node	1, 3, 2, 6, 4

The rule

Preorder, inorder and postorder are the same walk. The only difference is where the line that handles the node sits: before the two recursive calls, between them or after them.

Basic

One walk writes all three orders

To make that concrete, the walkthrough runs one recursive walk with all three lines in it, each writing to its own list. Watch when each list grows: preorder on the way down, inorder when the walk comes back from the left, postorder as it leaves a node for good.

Inorder on a binary search tree reads its values in sorted order, which is the most common reason to choose it.

Choosing one

Pick the order by what a node needs to know

Order	A node is handled	Typical use
Preorder	before its children	Copy a tree, or write it out so it can be rebuilt: each parent comes before its children
Inorder	after its whole left side	A search tree's values in sorted order; the kth smallest; checking the order
Postorder	after both children	Anything a node works out from its children: sizes, heights, sums, freeing the tree
Level order	after every node above it	Whatever is nearest the root first: each level's last node, the shallowest leaf

When a problem says "for every node, using its children's answers", that is postorder. When it says "by level" or "nearest", that is level order.

Medium

Level order uses a queue instead of recursion

Level order visits the root, then every node one level down, then the level below that, left to right. Recursion can't do this directly, because it finishes one subtree before starting the next. A queue can: take a node from the front, put its children at the back. Children of this level line up behind the rest of this level, so levels come out in order.

To keep levels apart, note the queue's length before each level starts. Exactly that many nodes belong to the current level.

Hard

A stack of your own replaces the call stack

Recursive traversals keep their place on the call stack. A very deep tree can overflow it, and an iterator that hands out one value at a time can't pause in the middle of a recursion. Both problems go away with an explicit stack.

For inorder: from the current node, push every node on the way down the left side. The top of the stack is then the smallest value not yet written. Pop it, write it, and repeat the same thing from its right child. Because the loop is yours, it can stop at any point: the walkthrough finds the kth smallest value and quits as soon as it is written.

The stack holds the nodes whose left side is still being written, which is one path from the root at most: O(h) space, the same as the recursion it replaces.

The cost

Every traversal is O(n) time; the space depends on the shape

Each node is handled once, so every order takes O(n) time. The memory differs. Preorder, inorder and postorder hold one path at a time, on the call stack or on your own stack: O(h), which is about log n for a bushy tree and n for a chain. Level order holds one level in its queue, and the bottom level of a full tree holds about half the nodes: O(n) in the worst case.

Check yourself

4 questions

1. Which order lists a binary search tree's values from smallest to largest?

2. To compute every node's height, which order do you need?

3. Level order needs which structure to hold the nodes waiting to be visited?

4. Why use an explicit stack for inorder instead of recursion?

Takeaways

Remember this

Preorder, inorder and postorder are one recursive walk; only the position of the line that handles the node changes.
Inorder lists a search tree in sorted order; postorder suits anything a node computes from its children.
Level order uses a queue, and the queue's length at the start of a level tells you how many nodes that level has.
An explicit stack does inorder without recursion, which avoids deep recursion and lets the walk pause.
Every traversal is O(n) time; depth-first orders use O(h) space, level order up to O(n).

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

1 more once you have practiced Hash tables & maps. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.