Binary Tree Traversals: Pre, In & Post-Order (Recursive & Iterative)
Deconstruct tree traversal algorithms. Contrast Depth-First Search (DFS) orderings, trace recursive call stacks, and implement iterative traversals using an explicit stack.
By the end, you’ll be able to…
- Implement Pre-order, In-order, and Post-order traversals recursively.
- Convert recursive traversals to iterative algorithms using java.util.ArrayDeque on the heap.
- Understand why In-order traversal of a Binary Search Tree produces sorted order.
01The Anatomy of a Binary Tree
A Binary Tree is a hierarchical non-linear data structure where each node has at most two children, referred to as the left child and right child. The topmost node is called the Root. Nodes with no children are called Leaf Nodes.
Traversing a tree requires visiting every node in a deterministic order. Unlike linear arrays, trees can be traversed in several Depth-First Search (DFS) sequences depending on when the current node's value is processed relative to its children: Pre-order (Node -> Left -> Right), In-order (Left -> Node -> Right), and Post-order (Left -> Right -> Node).
02Recursive Traversals and Invariant Meaning
Recursive tree traversals mirror the inductive structure of the tree. In In-order traversal, we recursively process the left subtree, process the node itself, and recursively process the right subtree.
Crucially: In-order traversal of a valid Binary Search Tree (BST) is mathematically guaranteed to visit values in strictly ascending sorted order! Post-order traversal (children first, node last) is utilized for bottom-up calculations (such as computing directory sizes or freeing memory in C++).
03Iterative Traversal with an Explicit Stack
In production systems with deeply unbalanced or skewed trees (e.g. 100,000 nodes deep), recursive traversals will crash the JVM with a StackOverflowError. Converting recursion into an iterative algorithm using an explicit java.util.ArrayDeque eliminates stack limits.
For iterative in-order traversal: we push nodes onto the stack while traveling left as far as possible. When left is null, we pop a node from the stack, record its value, and transition to its right child.
04Why This Matters in Production
Tree structures represent structured documents (HTML DOM trees, JSON ASTs, XML schemas), database index B-Trees, and decision trees in machine learning. Compilers convert your Java source code into an Abstract Syntax Tree (AST) before generating bytecode.
Mastering recursive and iterative tree traversal techniques ensures you can manipulate, analyze, and transform hierarchical documents without memory leaks or stack exhaustion.
05Production Architecture & Engineering Trade-Offs
Tree-based data structures provide the foundational indexing mechanism for database storage engines and file systems. However, maintaining balanced tree topology under continuous insertion and deletion workloads is non-trivial. While perfectly balanced trees guarantee O(log n) worst-case search latencies, the rotational overhead required to enforce strict balance factors can degrade write performance.
In production database engines such as PostgreSQL or MySQL InnoDB, B+ Trees are favored over binary search trees because their high branching factor minimizes disk I/O and aligns node sizes with operating system virtual memory page boundaries. When operating entirely in memory, Red-Black trees offer an optimal compromise by bounding rebalancing rotations to a small constant number.
The ideas worth keeping.
- Pre-order is Node-Left-Right, In-order is Left-Node-Right, Post-order is Left-Right-Node.
- In-order traversal on a BST produces elements in strictly ascending sorted order.
- Use an explicit ArrayDeque on the heap to prevent StackOverflowError during deep tree traversals.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Maximum Depth of Binary Tree
Write a method maxDepth(TreeNode root) that returns the maximum height of a binary tree in O(N) time.
Explore a worked solution
public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}The depth of any node is 1 plus the maximum depth of its left and right subtrees.
Exercise 2: Iterative Pre-order Traversal
Implement pre-order traversal iteratively using a Stack. Explain why the right child must be pushed onto the stack before the left child.
Explore a worked solution
public List<Integer> preorder(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val); if (node.right != null) stack.push(node.right); // Push right first! if (node.left != null) stack.push(node.left); // Left pops first! } return res;}Because a stack is LIFO, pushing the right child first ensures the left child pops first, preserving Pre-order sequence.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Maximum Depth of Binary Tree
Write a method maxDepth(TreeNode root) that returns the maximum height of a binary tree in O(N) time.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.