Level Order Traversal of Binary Tree — BFS Explained with Real Code

package io.thecodeforge.algorithms.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * Level order traversal (BFS) on a binary tree.
 * Returns a flat list of node values in BFS order.
 *
 * Time:  O(N) — every node visited exactly once.
 * Space: O(W) — W is the maximum width of the tree (worst case N/2).
 */
public class LevelOrderBasic {

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

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

    /**
     * Returns all node values in level-order (BFS order) as a flat list.
     * Think of it as reading the tree left-to-right, top-to-bottom.
     */
    public static List<Integer> levelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) {
            return result; // empty tree — nothing to traverse
        }

        // The queue is the engine. It holds nodes waiting to be processed.
        Queue<TreeNode> processingQueue = new ArrayDeque<>();
        processingQueue.offer(root); // seed the queue with the root

        while (!processingQueue.isEmpty()) {
            // Pull the oldest node (front of queue)
            TreeNode currentNode = processingQueue.poll();
            result.add(currentNode.value);

            // Push children to the BACK of the queue.
            // Left before right preserves left-to-right reading order.
            if (currentNode.left != null) {
                processingQueue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                processingQueue.offer(currentNode.right);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        /*
         * Building this tree:
         *
         *         10
         *        /  \
         *       5    15
         *      / \     \
         *     3   7    20
         */
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.right = new TreeNode(20);

        List<Integer> traversalResult = levelOrder(root);
        System.out.println("Level order traversal: " + traversalResult);
    }
}

package io.thecodeforge.algorithms.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * Level order traversal with per-level grouping.
 * Returns a list of lists — each inner list is one level.
 *
 * The key technique: snapshot queue.size() before the inner loop
 * to know exactly how many nodes belong to the current level.
 */
public class LevelOrderGrouped {

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

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

    /**
     * Returns nodes grouped by level.
     * Result: [[root], [level1 left to right], [level2 left to right], ...]
     */
    public static List<List<Integer>> levelOrderGrouped(TreeNode root) {
        List<List<Integer>> allLevels = new ArrayList<>();

        if (root == null) {
            return allLevels;
        }

        Queue<TreeNode> processingQueue = new ArrayDeque<>();
        processingQueue.offer(root);

        while (!processingQueue.isEmpty()) {
            // Snapshot: how many nodes are in THIS level right now?
            int nodesInCurrentLevel = processingQueue.size();
            List<Integer> currentLevelValues = new ArrayList<>();

            // Process ONLY the nodes that were in the queue when this level began.
            // Any children we add during this loop belong to the NEXT level.
            for (int i = 0; i < nodesInCurrentLevel; i++) {
                TreeNode currentNode = processingQueue.poll();
                currentLevelValues.add(currentNode.value);

                // These children go to the back — they'll be processed next iteration
                if (currentNode.left != null) {
                    processingQueue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    processingn
            allLevels.add(currentLevelValues); // commit this level's results
        }

        return allLevels;
    }

    /**
     * Bonus: Right-side view — just take the LAST element from each level group.
     * This is what you'd see if you looked at the tree from the right side.
     */
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightmostValues = new ArrayList<>();
        List<List<Integer>> levels = levelOrderGrouped(root);

        for (List<Integer> level : levels) {
            // The last node in each level is the rightmost visible node
            rightmostValues.add(level.get(level.size() - 1));
        }

        return rightmostValues;
    }

    public static void main(String[] args) {
        /*
         * Tree structure:
         *
         *         10
         *        /  \
         *       5    15
         *      / \     \
         *     3   7    20
         */Queue.offer(currentNode.right);
                }
            }\n        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.right = new TreeNode(20);

        System.out.println("Grouped level order: " + levelOrderGrouped(root));
        System.out.println("Right side view:     " + rightSideView(root));
    }
}

package io.thecodeforge.algorithms.tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * Finds the MINIMUM depth of a binary tree — the number of edges
 * from root to the nearest leaf node.
 *
 * This is a classic real-world variant: think of it as "how quickly
 * can I reach a decision node from the root?" (e.g., in a decision tree
 * or a game tree where you want the fastest win path).
 *
 * Key insight: BFS finds the shortest path FIRST. The moment we hit
 * a leaf node during level order traversal, we've found the minimum depth.
 * DFS would be wrong here — it might find a deep leaf before a shallow one.
 */
public class MinDepthFinder {

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

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

    // Helper wrapper to track a node AND its current depth together
    static class NodeWithDepth {
        TreeNode node;
        int depth;

        NodeWithDepth(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    /**
     * Returns the minimum depth: shortest path from root to any leaf.
     * A leaf is a node with NO children.
     */
    public static int findMinimumDepth(TreeNode root) {
        if (root == null) {
            return 0; // empty tree has no depth
        }

        Queue<NodeWithDepth> processingQueue = new ArrayDeque<>();
        processingQueue.offer(new NodeWithDepth(root, 1));

        while (!processingQueue.isEmpty()) {
            NodeWithDepth current = processingQueue.poll();
            TreeNode currentNode = current.node;
            int currentDepth = current.depth;

            // A leaf node has no children — this is our earliest exit point
            boolean isLeaf = (currentNode.left == null && currentNode.right == null);
            if (isLeaf) {
                // BFS guarantees this is the SHALLOWEST leaf we can find
                return currentDepth;
            }

            // Not a leaf — push existing children with incremented depth
            if (currentNode.left != null) {
                processingQueue.offer(new NodeWithDepth(currentNode.left, currentDepth + 1));
            }
            if (currentNode.right != null) {
                processingQueue.offer(new NodeWithDepth(currentNode.right, currentDepth + 1));
            }
        }

        return 0; // unreachable for a valid non-null tree, but satisfies compiler
    }

    public static void main(String[] args) {
        /*
         * Tree structure:
         *
         *         1
         *        / \
         *       2   3
         *      /
         *     4
         *    /
         *   5
         *
         * Minimum depth = 2 (path: 1 -> 3, where 3 is a leaf)
         * NOT 4 (path: 1 -> 2 -> 4 -> 5), even though that's the only
         * path DFS would fully explore first.
         */
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);  // <-- this is a leaf at depth 2
        root.left.left = new TreeNode(4);
        root.left.left.left = new TreeNode(5);

        int minimumDepth = findMinimumDepth(root);
        System.out.println("Minimum depth of tree: " + minimumDepth);

        /*
         * A fully balanced tree — min depth should equal max depth
         *
         *      10
         *     /  \
         *    5   15
         */
        TreeNode balancedRoot = new TreeNode(10);
        balancedRoot.left = new TreeNode(5);
        balancedRoot.right = new TreeNode(15);

        System.out.println("Min depth of balanced tree: " + findMinimumDepth(balancedRoot));
    }
}