High‑Frequency Interview Question: Java 17 BFS and DFS Traversals of a Binary Tree

When working with tree data structures, the most common operation is to visit every node, known as traversal. Tree‑related questions appear frequently in technical interviews and are essential to master.

Binary Tree Traversal Overview

Binary tree traversal falls into two major categories: breadth‑first search (BFS) and depth‑first search (DFS). DFS is further divided into preorder, inorder, and postorder based on when the root node is visited.

All four traversals only require two data structures: a queue for BFS and a stack for DFS.

Example Tree and Node Definition

The example tree has seven nodes: root A, second level B and C, third level D, E, F, G. B’s children are D and E; C’s children are F and G.

class TreeNode {
    char value;
    TreeNode left;
    TreeNode right;

    TreeNode(char value) {
        this.value = value;
    }
}

Java 17’s record cannot be used here because tree nodes need mutable left/right references.

static TreeNode buildTree() {
    var root = new TreeNode('A');
    root.left = new TreeNode('B');
    root.right = new TreeNode('C');
    root.left.left = new TreeNode('D');
    root.left.right = new TreeNode('E');
    root.right.left = new TreeNode('F');
    root.right.right = new TreeNode('G');
    return root;
}

All traversal methods use this tree for testing, collecting visited node values into a list.

Choosing Containers

Both queue and stack are implemented with ArrayDeque. The legacy Stack class adds synchronized overhead that is unnecessary for single‑threaded tree traversal, so ArrayDeque is preferred for speed.

Breadth‑First Traversal (Level Order)

BFS visits nodes layer by layer from left to right. The algorithm uses a queue (FIFO).

static List<Character> bfs(TreeNode root) {
    var result = new ArrayList<Character>();
    if (root == null) return result;
    var queue = new ArrayDeque<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        var node = queue.poll();
        result.add(node.value);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return result;
}

When adding children, the left child must be enqueued before the right child to preserve left‑to‑right order within the same level.

BFS by Level (LeetCode style)

static List<List<Character>> bfsByLevel(TreeNode root) {
    var result = new ArrayList<List<Character>>();
    if (root == null) return result;
    var queue = new ArrayDeque<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        var level = new ArrayList<Character>();
        for (int i = 0; i < size; i++) {
            var node = queue.poll();
            level.add(node.value);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Depth‑First Traversal (Recursive)

DFS explores a path to its deepest node before backtracking. The three variants differ only in the order of processing left subtree, root, and right subtree.

static void preorder(TreeNode node, List<Character> result) {
    if (node == null) return;
    result.add(node.value);
    preorder(node.left, result);
    preorder(node.right, result);
}

static void inorder(TreeNode node, List<Character> result) {
    if (node == null) return;
    inorder(node.left, result);
    result.add(node.value);
    inorder(node.right, result);
}

static void postorder(TreeNode node, List<Character> result) {
    if (node == null) return;
    postorder(node.left, result);
    postorder(node.right, result);
    result.add(node.value);
}

The position of result.add(node.value) determines preorder (first), inorder (middle), or postorder (last).

Iterative DFS Versions

Preorder (Iterative)

Replace the queue with a stack and push the right child before the left child so that the left child is processed first.

static List<Character> preorderIterative(TreeNode root) {
    var result = new ArrayList<Character>();
    if (root == null) return result;
    var stack = new ArrayDeque<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        var node = stack.pop();
        result.add(node.value);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

Running this on the example yields A B D E C F G.

Inorder (Iterative)

Use a stack to remember the path while walking leftward, then process nodes and shift to the right subtree.

static List<Character> inorderIterative(TreeNode root) {
    var result = new ArrayList<Character>();
    var stack = new ArrayDeque<TreeNode>();
    var current = root;
    while (!stack.isEmpty() || current != null) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        var node = stack.pop();
        result.add(node.value);
        current = node.right;
    }
    return result;
}

The example produces D B E A F C G.

Postorder (Iterative)

Perform a modified preorder (root‑right‑left) and reverse the result list.

static List<Character> postorderIterative(TreeNode root) {
    var result = new ArrayList<Character>();
    if (root == null) return result;
    var stack = new ArrayDeque<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        var node = stack.pop();
        result.add(node.value);
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    Collections.reverse(result);
    return result;
}

Only the order of pushing children differs from preorder, and the final reversal yields D E B F G C A.

Making the Tree Iterable (Lazy Evaluation)

Java lacks generators, but an Iterable implementation can provide similar lazy traversal. The iterator maintains a stack and yields nodes one by one.

class PreOrderWalker implements Iterable<TreeNode> {
    private final TreeNode root;

    PreOrderWalker(TreeNode root) { this.root = root; }

    @Override
    public Iterator<TreeNode> iterator() {
        var stack = new ArrayDeque<TreeNode>();
        if (root != null) stack.push(root);
        return new Iterator<TreeNode>() {
            @Override public boolean hasNext() { return !stack.isEmpty(); }
            @Override public TreeNode next() {
                if (stack.isEmpty()) throw new NoSuchElementException();
                var node = stack.pop();
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
                return node;
            }
        };
    }
}

Usage:

for (var node : new PreOrderWalker(root)) {
    System.out.print(node.value + " ");
}

This lazy approach uses constant additional memory per node and avoids building the whole result list up front, which is beneficial for very large trees.

Conclusion

Choose BFS when the problem is layer‑related (e.g., shortest path, minimum depth). Choose DFS for path‑ or subtree‑related tasks (e.g., serialization). Prefer recursive implementations for brevity unless the tree can be extremely deep, in which case the iterative version avoids stack overflow. Practicing the iterative inorder traversal is especially valuable because its stack‑based path‑recording pattern recurs in many tree‑related interview problems.