Chapter 17
Tree Traversals in Java
Java Data Structures & Algorithms Series
Tree Traversal means visiting every node in the tree in a specific order. There are two major categories
— DFS (Depth First Search) which goes deep before wide, and BFS (Breadth First Search) which goes
level by level.
1 The Tree We'll Use
We'll use this same tree for all traversals so you can compare outputs clearly.
1
/ \
2 3
/ \ \
4 5 6
/
7
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { [Link] = val; }
}
// Build tree
TreeNode root = new TreeNode(1);
[Link] = new TreeNode(2);
[Link] = new TreeNode(3);
[Link] = new TreeNode(4);
[Link] = new TreeNode(5);
[Link] = new TreeNode(6);
[Link] = new TreeNode(7);
2 DFS — Preorder Traversal (Root → Left → Right)
Visit root FIRST, then go left, then right.
1 ← visit 1 first
/ \
2 3 ← then go left subtree fully, then right
/ \ \
4 5 6
/
7
Preorder: [1, 2, 4, 5, 3, 6, 7]
Recursive (Simple)
public static void preorder(TreeNode root, List<Integer> result) {
if (root == null) return;
[Link]([Link]); // 1. Visit root
preorder([Link], result); // 2. Go left
preorder([Link], result); // 3. Go right
}
Iterative (Using Stack)
public static List<Integer> preorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
[Link](root);
while (![Link]()) {
TreeNode node = [Link]();
[Link]([Link]); // visit node
// Push right first so left is processed first (LIFO)
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
return result;
}
Time: O(n) | Space: O(h)
3 DFS — Inorder Traversal (Left → Root → Right)
Go all the way left first, visit root, then go right.
⭐ Key Property: Inorder on a BST always gives sorted output — this is the most important
property of BST traversal.
Inorder: [4, 2, 5, 1, 3, 7, 6]
Recursive
public static void inorder(TreeNode root, List<Integer> result) {
if (root == null) return;
inorder([Link], result); // 1. Go left
[Link]([Link]); // 2. Visit root
inorder([Link], result); // 3. Go right
}
Iterative (Using Stack)
public static List<Integer> inorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || ![Link]()) {
// Go as far left as possible
while (curr != null) {
[Link](curr);
curr = [Link];
}
curr = [Link](); // backtrack
[Link]([Link]); // visit
curr = [Link]; // move right
}
return result;
}
Time: O(n) | Space: O(h)
4 DFS — Postorder Traversal (Left → Right → Root)
Visit root LAST — process both children before the parent.
⭐ Key Use Cases: Used for deleting a tree (delete children before parent) and evaluating
expression trees.
Postorder: [4, 5, 2, 7, 6, 3, 1]
Recursive
public static void postorder(TreeNode root, List<Integer> result) {
if (root == null) return;
postorder([Link], result); // 1. Go left
postorder([Link], result); // 2. Go right
[Link]([Link]); // 3. Visit root last
}
Iterative (Using 2 Stacks)
public static List<Integer> postorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
[Link](root);
while (![Link]()) {
TreeNode node = [Link]();
[Link](node); // store in reverse order
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
while (![Link]()) [Link]([Link]().val); // pop s2 = postorder
return result;
}
Time: O(n) | Space: O(n)
5 BFS — Level Order Traversal (Queue-based)
Visit all nodes level by level, left to right.
⭐ Key Insight: Uses a Queue (FIFO) — add children to queue, process nodes one level at a
time.
Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5, 6]
Level 3: [7]
Output: [ [1], [2,3], [4,5,6], [7] ]
import [Link].*;
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link](); // number of nodes at current level
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
[Link]([Link]); // visit node
if ([Link] != null) [Link]([Link]); // enqueue
children
if ([Link] != null) [Link]([Link]);
}
[Link](level);
}
return result;
}
Time: O(n) | Space: O(n)
6 BFS Variants
Zigzag Level Order (Alternate left-right direction)
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
[Link](root);
boolean leftToRight = true;
while (![Link]()) {
int size = [Link]();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
// add to front or back based on direction
if (leftToRight) [Link]([Link]);
else [Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
leftToRight = !leftToRight; // flip direction each level
}
return result;
}
// Output: [ [1], [3,2], [4,5,6], [7] ]
Average of Each Level
public static List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
double sum = 0;
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
sum += [Link];
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](sum / size);
}
return result;
}
7 All Traversals at a Glance
Traversal Order Key Use Case Data Structure
Preorder Root → Left → Copy/serialize tree Stack
Right
Inorder Left → Root → BST sorted output Stack
Right
Postorder Left → Right → Delete tree, expression eval 2 Stacks
Root
Level Order Level by level Shortest path, print levels Queue
Zigzag Alternating BFS Interview favourite Queue + flag
8 Morris Traversal (Space Optimized — O(1) Space!)
Morris Inorder traversal uses no stack or recursion — it temporarily modifies the tree using threaded links,
then restores it.
💡 How it works: Finds the inorder predecessor (rightmost node in left subtree), creates a
temporary thread back to current node, traverses left, then removes the thread and visits the
node. Zero extra memory!
public static List<Integer> morrisInorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if ([Link] == null) {
[Link]([Link]); // no left child, visit and go right
curr = [Link];
} else {
// find inorder predecessor (rightmost node in left subtree)
TreeNode pred = [Link];
while ([Link] != null && [Link] != curr)
pred = [Link];
if ([Link] == null) {
[Link] = curr; // create thread
curr = [Link];
} else {
[Link] = null; // remove thread
[Link]([Link]);
curr = [Link];
}
}
}
return result;
}
Time: O(n) | Space: O(1) ← no stack, no recursion!
9 Full Runnable Java Program
import [Link].*;
class TreeNode {
int val; TreeNode left, right;
TreeNode(int v) { val = v; }
}
public class Chapter17TreeTraversals {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
[Link] = new TreeNode(2);
[Link] = new TreeNode(3);
[Link] = new TreeNode(4);
[Link] = new TreeNode(5);
[Link] = new TreeNode(6);
[Link] = new TreeNode(7);
List<Integer> pre = new ArrayList<>();
List<Integer> in = new ArrayList<>();
List<Integer> post = new ArrayList<>();
preorder(root, pre);
inorder(root, in);
postorder(root, post);
[Link]("Preorder: " + pre); // [1,2,4,5,3,6,7]
[Link]("Inorder: " + in); // [4,2,5,1,3,7,6]
[Link]("Postorder: " + post); // [4,5,2,7,6,3,1]
[Link]("Level Order: " + levelOrder(root));
[Link]("Zigzag: " + zigzagLevelOrder(root));
[Link]("Morris In: " + morrisInorder(root));
}
static void preorder(TreeNode r, List<Integer> res) {
if (r == null) return;
[Link]([Link]); preorder([Link], res); preorder([Link], res);
}
static void inorder(TreeNode r, List<Integer> res) {
if (r == null) return;
inorder([Link], res); [Link]([Link]); inorder([Link], res);
}
static void postorder(TreeNode r, List<Integer> res) {
if (r == null) return;
postorder([Link], res); postorder([Link], res); [Link]([Link]);
}
static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int sz = [Link]();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < sz; i++) {
TreeNode n = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
}
return res;
}
static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
boolean l2r = true;
while (![Link]()) {
int sz = [Link]();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < sz; i++) {
TreeNode n = [Link]();
if (l2r) [Link]([Link]);
else [Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level); l2r = !l2r;
}
return res;
}
static List<Integer> morrisInorder(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if ([Link] == null) { [Link]([Link]); curr = [Link]; }
else {
TreeNode pred = [Link];
while ([Link] != null && [Link] != curr) pred =
[Link];
if ([Link] == null) { [Link] = curr; curr = [Link];
}
else { [Link] = null; [Link]([Link]); curr =
[Link]; }
}
}
return res;
}
}
10 Practice Problems for Chapter 17
Solve in this order:
Easy Print all 4 traversals (Pre, In, Post, Level) for a given tree
Easy Find max value at each level using BFS
Medium Zigzag level order traversal (LeetCode #103)
Medium Binary tree right side view (LeetCode #199)
Medium Vertical order traversal (LeetCode #987)
Medium Construct binary tree from Preorder + Inorder (LeetCode #105)
Hard Serialize and deserialize a binary tree (LeetCode #297)
💡 Key Insight: DFS uses a Stack (explicit or recursion call stack), BFS uses a Queue — this
pattern repeats in Graphs (Chapters 20 & 21) at a much larger scale. Mastering traversals here
means Graph BFS/DFS will feel completely natural. Next up is Chapter 18 — BST, where
Inorder traversal becomes your most powerful weapon! 🚀
Prepared using Claude Sonnet 4.6 Thinking • Java Data Structures & Algorithms Series