Master all four tree traversal orders and know when to use each one.
A binary tree can be visited in four fundamental orders. Each order processes the root, left subtree, and right subtree in a different sequence. Understanding which to use is the key to solving most tree problems efficiently.
Consider this binary tree. Each traversal visits the same 7 nodes, but in a different order:
Key observation: InOrder traversal of a BST always gives nodes in sorted order. This is the single most important fact for BST problems.
Choosing the right traversal order is half the battle. Here is a quick reference for each:
Rule of thumb: If you need information from children before processing a node, use PostOrder. If you need to process a node before its children, use PreOrder. If you need sorted access in a BST, use InOrder. If you need level information, use LevelOrder.
Visit the root first, then recurse on the left subtree, then the right subtree. The root is always the first element in the output.
void preorder(TreeNode root, List<Integer> result) { if (root == null) return; result.add(root.val); // 1. Visit root preorder(root.left, result); // 2. Traverse left preorder(root.right, result); // 3. Traverse right }
For the tree [4, 2, 6, 1, 3, 5, 7], the recursive calls unfold like this:
preorder(4) // visit 4 preorder(2) // visit 2 preorder(1) // visit 1 preorder(null) // return preorder(null) // return preorder(3) // visit 3 preorder(null) // return preorder(null) // return preorder(6) // visit 6 preorder(5) // visit 5 preorder(null) // return preorder(null) // return preorder(7) // visit 7 preorder(null) // return preorder(null) // return // Output: 4 2 1 3 6 5 7
Recurse on the left subtree first, then visit the root, then the right subtree. For a BST, this produces elements in sorted ascending order.
void inorder(TreeNode root, List<Integer> result) { if (root == null) return; inorder(root.left, result); // 1. Traverse left result.add(root.val); // 2. Visit root inorder(root.right, result); // 3. Traverse right }
In a BST, every node in the left subtree is smaller and every node in the right subtree is larger. InOrder visits left first (all smaller values), then the node itself, then right (all larger values). This naturally produces sorted output:
Recurse on both subtrees before visiting the root. The root is always the last element in the output. This is ideal for bottom-up computations like calculating tree height.
void postorder(TreeNode root, List<Integer> result) { if (root == null) return; postorder(root.left, result); // 1. Traverse left postorder(root.right, result); // 2. Traverse right result.add(root.val); // 3. Visit root (last!) }
int height(TreeNode root) { if (root == null) return 0; int left = height(root.left); // get left height first int right = height(root.right); // get right height first return Math.max(left, right) + 1; // then process root }
You need the children's heights before you can compute the parent's height. That is the essence of PostOrder: bottom-up information flow.
Process nodes level by level from top to bottom using a queue. Unlike the DFS-based orders above, LevelOrder uses BFS and is naturally iterative.
List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); // nodes at this level List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; }
The size trick: Capturing queue.size() at the start of each iteration lets you process exactly one level at a time. Without this, you would not know where one level ends and the next begins.
Recursive solutions use the call stack implicitly. For iterative versions, we manage an explicit stack. Each traversal has a distinct stack strategy.
Push right child first, then left. Since a stack is LIFO, left gets processed before right.
List<Integer> preorderIterative(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // visit immediately if (node.right != null) stack.push(node.right); // right first! if (node.left != null) stack.push(node.left); // left on top } return result; }
Go left as far as possible, pushing each node. When you cannot go left, pop and visit, then go right.
List<Integer> inorderIterative(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { // go left as far as possible stack.push(curr); curr = curr.left; } curr = stack.pop(); // visit result.add(curr.val); curr = curr.right; // then go right } return result; }
Use a modified preorder (root, right, left) and reverse the result. This avoids the complexity of tracking whether both children have been visited.
List<Integer> postorderIterative(TreeNode root) { LinkedList<Integer> result = new LinkedList<>(); if (root == null) return result; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.addFirst(node.val); // add to FRONT (reverse) if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } return result; }
PostOrder trick explained: Normal preorder is Root-Left-Right. If we swap to Root-Right-Left and reverse the result, we get Left-Right-Root, which is PostOrder. Using addFirst reverses as we go, avoiding a separate reverse step.
Both recursive and iterative approaches use O(h) space for the stack. Morris Traversal achieves O(1) space by temporarily modifying the tree structure using threaded binary trees.
For each node, find its inorder predecessor (rightmost node in the left subtree). Create a temporary link from the predecessor back to the current node. This "thread" lets us return to the parent without a stack.
List<Integer> morrisInorder(TreeNode root) { List<Integer> result = new ArrayList<>(); TreeNode curr = root; while (curr != null) { if (curr.left == null) { result.add(curr.val); // no left subtree, visit curr = curr.right; } else { // Find inorder predecessor TreeNode pred = curr.left; while (pred.right != null && pred.right != curr) pred = pred.right; if (pred.right == null) { pred.right = curr; // create thread curr = curr.left; } else { pred.right = null; // remove thread result.add(curr.val); // visit curr = curr.right; } } } return result; }
When to use Morris: Only when space is a hard constraint. The constant factor is higher than stack-based approaches, and the temporary tree modification makes it unsuitable for concurrent access. For interviews, knowing it exists and how it works is usually sufficient.
These LeetCode problems directly test tree traversal patterns:
Step through each traversal order on the binary tree below. Watch which node is visited and how the stack or queue changes at each step.
All traversals visit each node exactly once, giving O(n) time. For space: recursive and iterative stack-based traversals use O(h) where h is the tree height (O(log n) for balanced, O(n) for skewed). LevelOrder uses a queue that can hold up to O(n) nodes (the widest level). Morris Traversal achieves O(1) auxiliary space by threading the tree.
h vs n: For a balanced binary tree, h = log(n). For a completely skewed tree (essentially a linked list), h = n. In interviews, stating O(h) shows you understand the distinction. For worst-case analysis, O(h) = O(n).