Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Trees in Java: Roots, Tree Types, DFS and BFS Traversals

Understand tree terminology and shapes, then learn inorder, preorder, postorder and level order with two larger examples, static dry runs and tested recursive and iterative Java.

BasicsTreesPattern: recursion

A folder contains other folders. An organisation has teams and subteams. A comment can have replies, and each reply can have its own replies.

These relationships are hierarchical: something sits above something else. A tree is a useful way to represent that hierarchy.

This guide has two parts. First, we learn what a tree contains and how to recognise its shape. Then we visit its nodes using DFS and BFS, with two larger examples and commented Java for both recursion and explicit work lists.

You need basic Java classes, loops and lists. The recursion guide explains what happens when a method pauses to call itself.

1. What makes a data structure a tree?

A tree contains nodes connected by edges. In a rooted tree, one node is chosen as the starting point: the root.

In the parent-to-child structure used here:

  • The root has no parent.
  • Every other node has exactly one parent.
  • Following child links cannot bring you back to an earlier node: there are no cycles.
  • Every node belongs to the hierarchy reachable from the root.

A nonempty tree with n nodes has n − 1 edges. There is one parent edge for each node except the root. An empty tree has no nodes; in Java, we represent it with root == null.

A general tree can have any number of children per node. A binary tree has at most two: a named left child and right child. One child is allowed, and its side matters.

Takeaway

Remember: binary means at most two, not “every node must have two.” A binary tree is also not automatically a binary search tree. A search tree adds rules about where values belong.

The rooted-tree terminology and the distinction between a binary tree and a binary search tree are described in Open Data Structures.

2. Root, children, leaves and ancestors

We will reuse this fifteen-node tree throughout the article.

Tree A: root 8 has children 4 and 12. Their children are 2, 6, 10 and 14. The final level contains 1, 3, 5, 7, 9, 11, 13 and 15, each connected to its parent.
Tree A has 15 nodes, 14 edges and four levels. Every node above the last level has two children.
Term Meaning Example in Tree A
Root The top node of the whole tree 8
Parent The node immediately above a child 6 is the parent of 7
Child A node one edge below its parent 4 and 12 are children of 8
Siblings Nodes with the same parent 5 and 7
Leaf A node with no children 1, 3, 5, 7, 9, 11, 13, 15
Internal node A node with at least one child 8, 4, 6
Ancestor A node above another node on its route to the root Ancestors of 7: 6, 4, 8
Descendant A node below another node 7 is a descendant of 4
Subtree A node together with all its descendants Subtree rooted at 4: 4, 2, 1, 3, 6, 5, 7
Edge One parent-child connection The connection from 4 to 6
Path Nodes connected along a route 8 → 4 → 6 → 7
Depth Number of edges from the root to a node Depth of 8 is 0; depth of 7 is 3
Height Longest downward path to a leaf, measured in edges Tree A has height 3; a leaf has height 0

Here, ancestor and descendant mean strictly above or below: a node is not counted as its own ancestor. A problem might explicitly use “ancestor or self,” so read its definition.

We number levels from 0, the same as depth. Some books call the root “level 1” or measure height in nodes. Neither convention changes a traversal; it changes the reported number. With our convention, an empty subtree has height −1, and a one-node tree has height 0.

A leaf is not “a node drawn at the bottom of the page.” A shorter branch can have a leaf higher up. A one-node tree’s root is also a leaf.

3. Five tree shapes you should recognise

These names describe different properties. They are not five mutually exclusive categories.

Full binary tree: zero or two children

Every node has either no children or exactly two. A node with only one child breaks the rule. This is also called a proper binary tree. NIST definition.

A full but unbalanced tree: 1 has children 2 and 3; 3 has children 4 and 5; 5 has children 6 and 7. Every node has zero or two children, but leaves occur at different depths.
Full does not mean every level is filled. This tree is full, but neither complete nor height-balanced.

Memory trick: full describes the number of children of each node: zero or two.

Complete binary tree: fill levels from left to right

All levels above the last are filled. The last level may be incomplete, but its nodes must occupy the leftmost available positions. You cannot leave a gap and then place a node farther right. NIST definition.

A complete six-node tree: root 1 has children 2 and 3; 2 has children 4 and 5; 3 has only a left child, 6. The last level fills its first three positions.
The final row contains 4, 5 and 6, with only the far-right position empty. Node 3 has one child, so this tree is complete but not full.

Memory trick: complete is about filling positions in level order, like filling seats from the left. Binary heaps use this shape; the heap’s value-order rule is a separate property.

Perfect binary tree: every level is filled

Every internal node has two children, and every leaf has the same depth. Tree A is perfect. So is the smaller tree below. NIST definition.

A perfect seven-node tree: 1 has children 2 and 3; 2 has children 4 and 5; 3 has children 6 and 7. All leaves are at depth 2.
Every position is occupied: one node, then two, then four.

For height h measured in edges, a perfect binary tree has 2^(h + 1) − 1 nodes and 2^h leaves. At height 3, that gives Tree A’s 15 nodes and 8 leaves.

Memory trick: perfect has no missing positions at any level.

Balanced binary tree: do not let one side become too tall

“Balanced” can refer to different balance rules. In this article, we mean height-balanced: at every node, the heights of its left and right subtrees differ by at most 1. This is the familiar local height condition discussed in USC’s tree material.

A height-balanced four-node tree: 1 has children 2 and 3; 2 has only a right child, 4. Every node's subtree heights differ by at most one.
Balanced does not mean identical sides or equal node counts. This tree is balanced but not complete: 2's left slot is empty before its occupied right slot.

At root 1, the left subtree has height 1 and the right subtree height 0. Their difference is 1. At node 2, the empty left subtree has height −1 and its right leaf height 0: again a difference of 1.

Checking only the root is not enough. A badly leaning subtree can exist farther down even when the root’s two heights match.

Memory trick: balanced compares heights at every node, not how symmetrical the drawing looks. Height balance keeps the tree height logarithmic in the number of nodes; it does not make a traversal skip nodes.

Degenerate tree: a linked-list-like chain

Every non-leaf node has only one child. There is no branching choice, so a tree with n nodes has height n − 1.

A degenerate four-node chain: 1's right child is 2, 2's left child is 3, and 3's right child is 4. Every non-leaf node has exactly one child.
A degenerate tree can zigzag. Entirely left-leaning and entirely right-leaning chains are special cases, called skewed trees.

This shape matters for Java: a recursive method may need one call frame per node and eventually exceed the JVM’s stack limit.

Put the names together

Shape What to check What it does not guarantee
Full Every node has 0 or 2 children Equal heights or filled levels
Complete All earlier levels filled; last level left-packed Two children at every internal node
Perfect Every internal node has 2 children; all leaves at one depth Any ordering of the stored values
Height-balanced Subtree heights differ by at most 1 at every node Complete levels or equal node counts
Degenerate Every non-leaf node has exactly 1 child Fast search or shallow recursion

Every nonempty perfect binary tree is also full, complete and height-balanced. The reverse implications do not all hold. A binary search tree is about values, while these classifications are about shape. Different textbooks sometimes reuse the names differently; the definitions above are the conventions used here.

4. Traversal means choosing when to record a node

A traversal visits all nodes in an organised order. In our code, visit means order.add(node.value)—not merely entering a recursive method.

There are two main strategies:

  • DFS, depth-first search: follow a branch and finish its work before moving to another branch. Recursion uses Java’s call stack; an iterative version uses an explicit stack.
  • BFS, breadth-first search: finish one depth level before the next. The usual implementation uses a FIFO queue.

For binary trees, the three standard left-before-right DFS orders differ in where the current subtree’s root is recorded:

Traversal Order Where is the current root? Memory trick
Preorder Root → Left subtree → Right subtree First Pre = before the children
Inorder Left subtree → Root → Right subtree Between the subtrees In = in between
Postorder Left subtree → Right subtree → Root Last Post = after the children
Level order Level 0, then 1, then 2, and so on Before deeper levels A queue serves the oldest waiting node

Write N L R, L N R, L R N, where N is the current node. Move N; keep L before R.

The rule applies again at every subtree. Inorder at node 4 is “the whole subtree of 2, then 4, then the whole subtree of 6.” The 4 is a subtree root even though 8 is the root of the entire tree.

Takeaway

Remember: “go extremely left” is a useful starting action, not the complete inorder rule. After recording a node, finish its right subtree before returning to its waiting parent. Do not jump straight from the leftmost leaf to the whole tree’s root.

These are the common binary-tree DFS orders, not the only conceivable DFS visiting conventions. We consistently choose left before right. A general tree with many children has no single standard “middle child,” so ordinary binary-tree inorder should not be applied to it without a definition.

5. Our second example: missing children, still a valid tree

Tree B has thirteen nodes. Notice that 40 and 60 have a right child but no left child.

Tree B: 10 has children 20 and 30. 20 has children 40 and 50; 30 has children 60 and 70. 40 has only right child 80; 50 has children 90 and 100; 60 has only right child 110; 70 has children 120 and 130.
Tree B is height-balanced but not full, complete or perfect. It is not a binary search tree: for example, 10's left child is 20.

We will show both Tree A and Tree B for every traversal. The uneven example prevents us from memorising only the pattern of a perfect drawing.

The shared Java node

Java
public static final class TreeNode {
    public final int value; // The value is data; it does not determine child positions.
    public TreeNode left;  // null means that this child does not exist.
    public TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }
}

The methods below return lists rather than printing during traversal. That makes the results easy to compare, test and reuse. They do not change any child references. A null root returns an empty list.

Download the complete runnable Java file. It includes the imports, the exact two tree builders, every method below and a main method. The excerpts belong inside that file’s TreeTraversalExamples class. The examples use Java 21+ and ArrayList, ArrayDeque, Deque, Queue and List from java.util.

These methods assume a genuine tree: no cycles and no child object shared by two parents. A visited set is not needed when following only its left/right child links. The graph BFS/DFS guide explains why graphs need additional discovery tracking.

6. Inorder: left subtree, root, right subtree

Ask: “What must be finished before this node’s value is recorded?” For inorder, the answer is its entire left subtree.

Two worked examples

Tree A: finish the subtree rooted at 4, record 8, then finish the subtree rooted at 12:

Worked example · read from top to bottom
Left of 8:  1, 2, 3, 4, 5, 6, 7
Root:       8
Right of 8: 9, 10, 11, 12, 13, 14, 15

Inorder A: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

For the left subtree itself, apply the same rule: subtree 2 produces 1,2,3; then record 4; subtree 6 produces 5,6,7.

Tree B: node 40 has no left child, so record 40; its right subtree 80 must finish before returning to 20:

Worked example · read from top to bottom
Left of 10:  40, 80, 20, 90, 50, 100
Root:        10
Right of 10: 60, 110, 30, 120, 70, 130

Inorder B: 40, 80, 20, 90, 50, 100, 10, 60, 110, 30, 120, 70, 130

Tree A’s output happens to be sorted because Tree A is a binary search tree. Tree B shows the important distinction: inorder does not sort an arbitrary binary tree.

Recursive Java

Java
public static List<Integer> inorderRecursive(TreeNode root) {
    List<Integer> order = new ArrayList<>(); // One result shared by the recursive calls.
    inorder(root, order);
    return order;
}

private static void inorder(TreeNode node, List<Integer> order) {
    if (node == null) return; // An empty subtree contributes no values.
    inorder(node.left, order); // Finish the entire left subtree, not just its leftmost node.
    order.add(node.value); // IN: record this node between its two subtrees.
    inorder(node.right, order); // Finish the entire right subtree before returning.
}

Entering inorder(8) does not record 8. That frame pauses at its left call. The calls descend 8 → 4 → 2 → 1 → null. The null call returns immediately; then 1 can be recorded.

Where execution resumes What happens next Output so far
1, after its null left call Record 1; its null right call returns 1
2, after subtree 1 Record 2, then finish subtree 3 1,2,3
4, after subtree 2 Record 4, then finish subtree 6 1,2,3,4,5,6,7
8, after subtree 4 Now record 8 1,2,3,4,5,6,7,8
Subtree 12 Repeat the same left-root-right promise 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

Iterative Java: remember the waiting ancestors

The stack replaces the paused recursive frames. Push nodes while going left. When left is exhausted, pop a node, record it, and begin its right subtree.

Java
public static List<Integer> inorderIterative(TreeNode root) {
    List<Integer> order = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>(); // Ancestors waiting for their inorder turn.
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) { // Stop only when no subtree or ancestor remains.
        while (current != null) {
            stack.push(current); // Save where to return after this left subtree.
            current = current.left; // Keep moving left before recording a value.
        }
        TreeNode node = stack.pop(); // Its left subtree is now finished.
        order.add(node.value); // Record the current subtree root in the middle.
        current = node.right; // Explore this right subtree before the next waiting ancestor.
    }
    return order; // A null root naturally produces an empty list.
}

Here is the opening of Tree B’s dry run. Stack notation is bottom → top, so the rightmost entry is popped first.

Action Waiting stack Output
Push 10, 20, 40; left becomes null [10,20,40] []
Pop and record 40; move to its right child 80 [10,20] [40]
Push 80; its left is null [10,20,80] [40]
Pop and record 80; its right is null [10,20] [40,80]
Pop and record 20; begin its right subtree 50 [10] [40,80,20]
Push 50, then 90; pop and record 90 [10,50] [40,80,20,90]
Record 50, then finish 100 [10] [40,80,20,90,50,100]
Pop and record 10; begin subtree 30 [] [40,80,20,90,50,100,10]

Continue in the same way to obtain the complete Inorder B result above. An empty stack alone is not a stopping condition: current may still point to a right subtree.

7. Preorder: root, left subtree, right subtree

Ask: “Does the current node need to be recorded before its children?” If yes, preorder is the natural order.

Two worked examples

Tree A: record 8 immediately, then finish all of subtree 4, then all of subtree 12:

Worked example · read from top to bottom
Root:       8
Left of 8:  4, 2, 1, 3, 6, 5, 7
Right of 8: 12, 10, 9, 11, 14, 13, 15

Preorder A: 8, 4, 2, 1, 3, 6, 5, 7, 12, 10, 9, 11, 14, 13, 15

Tree B: record 10, then 20, then 40. 40 has no left child, so explore its right child 80 before moving back to subtree 50:

Worked example · read from top to bottom
Root:        10
Left of 10:  20, 40, 80, 50, 90, 100
Right of 10: 30, 60, 110, 70, 120, 130

Preorder B: 10, 20, 40, 80, 50, 90, 100, 30, 60, 110, 70, 120, 130

Recursive Java

Java
public static List<Integer> preorderRecursive(TreeNode root) {
    List<Integer> order = new ArrayList<>();
    preorder(root, order);
    return order;
}

private static void preorder(TreeNode node, List<Integer> order) {
    if (node == null) return; // There is no node to record or explore.
    order.add(node.value); // PRE: record this node before exploring its children.
    preorder(node.left, order); // Complete the left subtree first.
    preorder(node.right, order); // Then complete the right subtree.
}

Compare this with inorder: the two recursive calls keep their left-before-right order. We only moved order.add before both calls.

Iterative Java: push right before left

Because a stack is last in, first out, the last child pushed is processed first. To visit left first, push right first.

Java
public static List<Integer> preorderIterative(TreeNode root) {
    List<Integer> order = new ArrayList<>();
    if (root == null) return order; // ArrayDeque must not receive a null element.
    Deque<TreeNode> stack = new ArrayDeque<>(); // Subtree roots that still need processing.
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop(); // Choose the most recently scheduled subtree.
        order.add(node.value); // PRE: record its root immediately.
        if (node.right != null) stack.push(node.right); // Push right first: it must wait below left.
        if (node.left != null) stack.push(node.left); // Left is on top, so it is processed next.
    }
    return order;
}

The opening steps for Tree A, again showing the stack bottom → top:

Node popped and recorded Stack after scheduling children Output
8 [12,4] [8]
4 [12,6,2] [8,4]
2 [12,6,3,1] [8,4,2]
1 [12,6,3] [8,4,2,1]
3 [12,6] [8,4,2,1,3]
6 [12,7,5] [8,4,2,1,3,6]

For Tree B, the same logic schedules [30,20] after 10, then [30,50,40] after 20, then [30,50,80] after 40. The output begins 10,20,40,80, exactly as the recursive version does.

Preorder is useful when a parent needs to be handled before descendants, such as writing a hierarchical structure. Reconstructing a general tree from only its value sequence is not guaranteed: serialization also needs structural information, such as null-child markers.

8. Postorder: left subtree, right subtree, root

Ask: “Do I need both children’s answers before handling this node?” That is the central postorder idea.

For example, to compute a subtree’s size, first compute the sizes of its left and right subtrees, then combine them with the current node. The size calculation uses postorder’s dependency order, even if it does not print a traversal list.

Two worked examples

Tree A: finish both subtrees before recording 8:

Worked example · read from top to bottom
Left of 8:  1, 3, 2, 5, 7, 6, 4
Right of 8: 9, 11, 10, 13, 15, 14, 12
Root:       8

Postorder A: 1, 3, 2, 5, 7, 6, 4, 9, 11, 10, 13, 15, 14, 12, 8

Notice 1,3,2: both children are recorded before their parent 2. Then 5,7,6, then their waiting parent 4.

Tree B: 40 has no left child, but its right child 80 still has to finish before 40:

Worked example · read from top to bottom
Left of 10:  80, 40, 90, 100, 50, 20
Right of 10: 110, 60, 120, 130, 70, 30
Root:        10

Postorder B: 80, 40, 90, 100, 50, 20, 110, 60, 120, 130, 70, 30, 10

Recursive Java

Java
public static List<Integer> postorderRecursive(TreeNode root) {
    List<Integer> order = new ArrayList<>();
    postorder(root, order);
    return order;
}

private static void postorder(TreeNode node, List<Integer> order) {
    if (node == null) return; // The empty subtree is already finished.
    postorder(node.left, order); // Finish the left child and all its descendants.
    postorder(node.right, order); // Finish the right child and all its descendants.
    order.add(node.value); // POST: record this node only after both sides finish.
}

The result line moved after both recursive calls. No reversal of a preorder list is involved.

Iterative Java: do not remove a parent too early

Inorder could record a node after finishing its left side. Postorder must wait for both sides. We need one additional piece of state: lastVisited, the exact node most recently recorded.

  1. Push nodes while descending left.
  2. Peek at a waiting node without removing it.
  3. If its right child exists and has not finished, explore that child.
  4. Otherwise, both sides are finished: record and pop the node.
Java
public static List<Integer> postorderIterative(TreeNode root) {
    List<Integer> order = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>(); // Nodes whose subtrees are not both finished yet.
    TreeNode current = root;
    TreeNode lastVisited = null; // The exact node most recently recorded, not just its value.

    while (current != null || !stack.isEmpty()) {
        if (current != null) {
            stack.push(current); // Remember this node, but do not record it yet.
            current = current.left; // Finish its left subtree first.
        } else {
            TreeNode node = stack.peek(); // Inspect the waiting node without removing it.
            if (node.right != null && lastVisited != node.right) {
                current = node.right; // Its right subtree exists and has not finished.
            } else {
                order.add(node.value); // Both subtrees are finished, so POST may record this node.
                lastVisited = stack.pop(); // Tell the waiting parent which child just finished.
            }
        }
    }
    return order;
}

Why compare references? Different nodes may contain the same value. lastVisited != node.right asks whether this particular child object has finished, not whether an equal number appeared somewhere else.

When a right subtree finishes in postorder, its root is the last node recorded in that subtree. That is why comparing to node.right is sufficient.

Dry run: Tree B’s left subtree

These are grouped operations, not one row per Java statement. Stack entries run bottom → top.

Operation Waiting stack afterwards Output so far
Push 10, 20, 40; left is empty [10,20,40] []
40 has unfinished right child 80; push it [10,20,40,80] []
80 has no children: record it; lastVisited = 80 [10,20,40] [80]
40.right == lastVisited: record 40 [10,20] [80,40]
20 still needs its right subtree: push 50, then 90 [10,20,50,90] [80,40]
Finish 90, then the right child 100 [10,20,50] [80,40,90,100]
Both children of 50 are done: record 50 [10,20] [80,40,90,100,50]
20.right == lastVisited: record 20 [10] [80,40,90,100,50,20]

The root 10 is still waiting: its right subtree 30 has not finished. For Tree A, the same waiting rule produces 1,3,2 before 4 can finish, and keeps 8 waiting until the final position.

A two-stack postorder implementation is another valid option: build a root-right-left order, then reverse it. Its additional stack storage can be O(n). The one-stack version above remembers the current ancestor path instead.

9. BFS: level-order traversal with a queue

DFS asks which branch to finish. BFS asks which level to finish.

A queue is first in, first out. A child is added behind nodes already waiting, so it cannot jump ahead of them. We enqueue left before right to preserve left-to-right order within each level.

Two worked examples

Tree A:

Worked example · read from top to bottom
Level 0: [8]
Level 1: [4, 12]
Level 2: [2, 6, 10, 14]
Level 3: [1, 3, 5, 7, 9, 11, 13, 15]

Level-order A: [[8], [4,12], [2,6,10,14], [1,3,5,7,9,11,13,15]]

Tree B: missing children do not become entries in the output.

Worked example · read from top to bottom
Level 0: [10]
Level 1: [20, 30]
Level 2: [40, 50, 60, 70]
Level 3: [80, 90, 100, 110, 120, 130]

Level-order B: [[10], [20,30], [40,50,60,70], [80,90,100,110,120,130]]

Flattening these lists gives the ordinary BFS visiting sequence. Keeping them grouped is useful for level averages, left/right views and “one answer per level” problems.

Iterative Java: freeze the size of the current level

Java
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels; // An empty tree has no levels to return.
    Queue<TreeNode> queue = new ArrayDeque<>(); // FIFO keeps shallower nodes ahead of deeper ones.
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // Freeze this count BEFORE adding the next level's children.
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) { // Remove exactly the nodes in the current level.
            TreeNode node = queue.poll(); // Process the oldest waiting node.
            level.add(node.value);
            if (node.left != null) queue.offer(node.left); // Keep left-to-right order within a level.
            if (node.right != null) queue.offer(node.right);
        }
        levels.add(level); // Keep level boundaries, rather than returning one flat sequence.
    }
    return levels;
}

The Java ArrayDeque documentation prohibits null elements. That is why we check the root and children before adding them. No null marker is needed: levelSize already identifies the boundary.

Dry run: Tree A, one complete level per iteration

The queue is shown front → rear. Unlike our stack tables, the leftmost entry is removed first.

Queue before this level Fixed levelSize Values recorded Queue after this level
[8] 1 [8] [4,12]
[4,12] 2 [4,12] [2,6,10,14]
[2,6,10,14] 4 [2,6,10,14] [1,3,5,7,9,11,13,15]
[1,3,5,7,9,11,13,15] 8 [1,3,5,7,9,11,13,15] []

Dry run: inside Tree B’s third level

Start with queue [40,50,60,70] and freeze levelSize = 4.

Node removed Children added Queue afterwards
40 Right child 80 [50,60,70,80]
50 90, then 100 [60,70,80,90,100]
60 Right child 110 [70,80,90,100,110]
70 120, then 130 [80,90,100,110,120,130]

Stop this inner loop after its four removals. The remaining six nodes belong to the next level. If you use a changing queue.size() as the loop limit, newly added children can incorrectly affect when the level ends.

Recursive BFS: keep the queue, recurse once per level

Recursion does not automatically make an algorithm DFS. In this version, each call finishes one whole queued level before calling the next one. The queue still controls the visiting order.

Java
public static List<List<Integer>> levelOrderRecursive(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new ArrayDeque<>(); // The queue still determines BFS order.
    queue.offer(root);
    collectNextLevel(queue, levels);
    return levels;
}

private static void collectNextLevel(Queue<TreeNode> queue, List<List<Integer>> levels) {
    if (queue.isEmpty()) return; // No next level remains: stop the recursion.
    int levelSize = queue.size(); // Each call handles exactly one complete level.
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        level.add(node.value);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    levels.add(level);
    collectNextLevel(queue, levels); // The call stack grows once per level; Java does not erase it.
}

Both implementations produce the two grouped outputs above. Prefer the iterative queue version in ordinary Java code: the recursive driver adds call-stack usage without improving the traversal.

A different technique runs ordinary DFS and appends values to a list indexed by depth. It can produce the same grouped result, but its execution order is still DFS, not BFS. Distinguish the order of computation from the final arrangement of the output.

10. Run both examples and compare the results

The companion’s exampleA() and exampleB() builders create exactly the diagrams shown above. Its entry point is:

Java
public static void main(String[] args) {
    TreeNode a = exampleA(); // Builds the exact fifteen-node Tree A shown in the article.
    TreeNode b = exampleB(); // Builds the exact thirteen-node Tree B, including its missing children.
    for (TreeNode root : List.of(a, b)) {
        System.out.println("Inorder recursive: " + inorderRecursive(root));
        System.out.println("Inorder iterative: " + inorderIterative(root));
        System.out.println("Preorder recursive: " + preorderRecursive(root));
        System.out.println("Preorder iterative: " + preorderIterative(root));
        System.out.println("Postorder recursive: " + postorderRecursive(root));
        System.out.println("Postorder iterative: " + postorderIterative(root));
        System.out.println("BFS levels: " + levelOrder(root));
        System.out.println("Recursive BFS levels: " + levelOrderRecursive(root));
    }
}

Compile TreeTraversalExamples.java with javac TreeTraversalExamples.java, then run java TreeTraversalExamples. The first eight lines are Tree A; the next eight are Tree B. Each recursive/iterative pair must agree with its complete worked example above.

Try replacing a builder result with null: all methods return []. For a single node containing 42, every DFS returns [42], and both level-order methods return [[42]].

11. Why the traversals work

Recursive DFS: an empty subtree contributes nothing. Suppose the recursive calls correctly traverse each child subtree. Recording the current node before, between or after those calls creates exactly preorder, inorder or postorder for the larger subtree. This argument applies repeatedly up to the whole tree.

Iterative inorder: the stack stores ancestors whose inorder turn is waiting. Descending left postpones recording them; popping happens only when the left subtree is complete. Moving to the popped node’s right subtree finishes that subtree before any older ancestor is recorded.

Iterative preorder: the top stack entry is the next subtree to start. Recording its root immediately gives “root first.” Pushing right before left puts the entire left traversal ahead of the waiting right subtree.

Iterative postorder: a waiting node is popped only when its left subtree is done and its right subtree is either absent or the subtree whose root was just recorded. Its descendants therefore appear before it, and lastVisited prevents re-entering its completed right subtree.

BFS: at the beginning of each outer iteration, the queue contains the next level in left-to-right order. Removing exactly that many nodes and appending their children constructs the next level in the same order. The recursive BFS driver preserves this identical queue invariant.

In a valid tree, every non-root node has one parent, so each child is scheduled once. No traversal needs to modify links or use node values to decide which child comes next.

12. Time and space complexity

Let n be the number of nodes, h the height in edges, and w the maximum number of nodes in any one level.

Approach Time Auxiliary space, excluding output Why
Recursive inorder / preorder / postorder O(n) O(h + 1) One active call path, plus the null base call
Iterative inorder / preorder / one-stack postorder O(n) O(h + 1) upper bound Waiting ancestors or subtree roots
Iterative queue BFS O(n) O(w) for a nonempty tree The frontier can contain parts of two adjacent levels
Recursive queue BFS O(n) O(w + h + 1) The frontier plus one waiting call per level

Every method returns O(n) output: a flat list for DFS or lists grouped by level for BFS. Include that if a question asks for total space, not just auxiliary space. An empty tree takes constant time and space.

Why are the nested loops in iterative inorder and BFS not O(n²)? A node is not newly processed for every outer iteration. It is pushed/enqueued once and popped/dequeued once. Postorder may inspect a waiting node more than once, but only a constant number of times around its two children. ArrayDeque end operations and ArrayList.add have amortized constant cost.

On a height-balanced tree, DFS’s height bound is O(log n). On a chain, recursive DFS and iterative inorder/postorder can need O(n) stack space. Iterative preorder can use less: a one-child chain has only one pending node in its stack. The table gives an upper bound, not a claim that every shape fills it.

A wide perfect tree can give BFS a frontier proportional to n; a single chain keeps its queue at size 1. Choose the work list based on the problem, not on a blanket claim that BFS or DFS always uses less memory.

13. When should you use each traversal?

What the problem needs Useful starting point Why
Ordered values from a valid BST Inorder Its left-root-right structure follows the BST ordering rule
Parent information before descendants Preorder The current root is available before its children
A result that depends on both child results Postorder Children finish before their parent is combined
Levels, level averages, nearest depth or views BFS Depth boundaries are explicit in the queue loop
Root-to-leaf paths or branch exploration DFS The active path follows one branch at a time

These are recognition clues, not rigid laws. For example, a right-side view can be solved with BFS or with a carefully ordered DFS. Ask what information must be available when you handle the current node.

14. Common mistakes and a quick self-check

  • “A binary tree must have two children everywhere.” No: zero, one or two are allowed.
  • Confusing full with complete. Full checks child counts; complete checks occupied positions.
  • Calling a tree balanced because only its root is balanced. The height condition must hold at every node.
  • Treating inorder as three individual nodes. L and R mean complete subtrees, not just extreme leaves.
  • Calling every recursive entry a visit. In inorder and postorder, recording happens later.
  • Pushing left before right in iterative preorder. A LIFO stack would process right first.
  • Popping a postorder parent before finishing its right subtree. Peek first, and track the completed child object.
  • Comparing lastVisited.value to a child’s value. Equal numbers do not mean identical nodes.
  • Adding null to an ArrayDeque. Guard missing children instead.
  • Using a changing queue size for the current BFS level. Save levelSize before adding children.
  • Expecting sorted output from any inorder traversal. Sorted order requires an appropriate BST value invariant.

Before looking back, answer these:

  1. In Tree A, name the ancestors of 7. Why is 5 not one?
  2. In Tree B, why does inorder begin 40,80,20, rather than 40,20,80?
  3. Why is 10 the first value in Tree B’s preorder but the last in its postorder?
  4. After processing Tree B’s node 40 in BFS, why must 50 be processed before 80?
  5. Can a tree be complete but not full? Which six-node example above demonstrates it?

Answers: 6,4,8; 5 is a sibling of 7, not above it. Inorder must finish 40’s right subtree before returning to 20. Preorder records a subtree root before its children, while postorder records it after them. BFS already has 50 waiting ahead of newly enqueued 80. The complete example has node 3 with exactly one child, 6.

The shortest revision note is: Pre = root first; In = root between; Post = root last; BFS = one level at a time. Apply the rule to every subtree, not just the root drawn at the top.

Practice next

Next lessonBFS and DFS in Java

Extend tree traversal to graphs, discovery tracking and shortest paths.

Back to Trees →