Level Order Traversal - DFS Min Depth Bug in Fraud Engine

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));
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class RecursiveLevelOrder {
    static class Node {
        int data;
        Node left, right;
        Node(int data) { this.data = data; }
    }

    private void traverse(Node node, int level, List<List<Integer>> result) {
        if (node == null) return;
        if (result.size() <= level) result.add(new ArrayList<>());
        result.get(level).add(node.data);
        traverse(node.left, level + 1, result);
        traverse(node.right, level + 1, result);
    }

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        traverse(root, 0, result);
        return result;
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class IterativeBFSGrouping {
    static class Node {
        int data;
        Node left, right;
        Node(int data) { this.data = data; }
    }

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();
                currentLevel.add(node.data);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(currentLevel);
        }
        return result;
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class ZigzagLevelOrder {
    static class Node {
        int data;
        Node left, right;
        Node(int data) { this.data = data; }
    }

    public List<List<Integer>> zigzagOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            LinkedList<Integer> currentLevel = new LinkedList<>();

            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();
                if (leftToRight) currentLevel.addLast(node.data);
                else currentLevel.addFirst(node.data);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

// io.thecodeforge — dsa tutorial

class LevelOrderComparison {
    // BFS uses O(width) queue — safe for wide trees
    void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            System.out.print(node.val + " ");
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
    }
    // DFS (inorder) uses O(depth) stack — risk of overflow
    void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.val + " ");
        inorder(node.right);
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

class LevelOrderMultilang {
    // Java BFS — works as blueprint for Python/C++
    void traverse(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            System.out.print(cur.val);               // process
            if (cur.left != null) q.add(cur.left);   // null check
            if (cur.right != null) q.add(cur.right);
        }
    }
    // Equivalent Python: q = deque([root]) then q.popleft()
    // Equivalent C++: queue<TreeNode*> q; front() then pop()
}