Tree BFS / Level Order Traversal

1. 1.Binary Tree Level Order Traversal
   Snapshot levelSize = len(queue) before inner loop: process level nodes into level slicemedium
2. 2.Binary Tree Zigzag Level Order Traversal
   Level order + boolean flag leftToRight: reverse level slice on alternate levelsmedium
3. 3.Binary Tree Right Side View
   Level order: append last node of each level slice (i == levelSize - 1)medium
4. 4.Average of Levels in Binary Tree
   Level order: sum level values and append sum / float64(levelSize)easy
5. 5.Minimum Depth of Binary Tree
   BFS early stop: return level depth as soon as first leaf (Left == nil && Right == nil) is popped!easy
6. 6.Maximum Width of Binary Tree
   Positional 1-based indexing (2*i, 2*i+1): width = rightPos - leftPos + 1 at each levelmedium
7. 7.Find Largest Value in Each Tree Row
   Level order: track max value across each level slicemedium
8. 8.Populating Next Right Pointers in Each Node
   Level order: set node.Next = nextNodeInLevel (prevNode.Next = currNode)medium
9. 9.Populating Next Right Pointers II
   Level order handling non-perfect binary trees, or pointer traversalmedium
10. 10.Cousins in Binary Tree
    Level order: track parent pointers & depth, confirm same depth but different parentseasy
11. 11.Even Odd Tree
    Level order checking strict index parity & strictly increasing/decreasing values per levelmedium
12. 12.Check Completeness of a Binary Tree
    BFS queue including nil nodes: once a nil is popped, no non-nil node can ever appear!medium
13. 13.Add One Row to Tree
    BFS stop at target depth - 1: insert new nodes between parent & left/right childrenmedium
14. 14.Deepest Leaves Sum
    Level order sum: sum of nodes at final level slicemedium
15. 15.Find Bottom Left Tree Value
    Level order: store first node of each level (i == 0)medium

1. 16.N-ary Tree Level Order Traversal
   Level order pushing all children slice (for _, child := range node.Children)medium
2. 17.Reverse Level Order Traversal
   Level order storing level slices, then reverse the result array at the endmedium
3. 18.Vertical Order Traversal
   BFS tracking (col, row) coordinates + sort by col then row then valuemedium
4. 19.Bottom View of Binary Tree
   BFS column map overwriting values col by col from top to bottommedium
5. 20.Top View of Binary Tree
   BFS column map storing only first node seen per columnmedium
6. 21.Nodes at Distance K
   BFS from target node after building graph / parent pointersmedium
7. 22.Maximum Level Sum of a Binary Tree
   Level order: track level sum & return 1-based level index with maximum summedium
8. 23.Minimum Number of Operations to Sort a Binary Tree by Level
   Level order + min cycle swaps algorithm to sort each level slicemedium

How to Think

1. Need level by level traversal?Tree BFS + Queue (FIFO)
2. Need nearest / minimum depth?BFS (reaches shallow nodes first)
3. Need rightmost node of every level?Level Order + last element (i == levelSize - 1)
4. Need largest / average / sum per level?BFS + levelSize aggregation loop
5. Need zigzag order?BFS + alternate level direction flag

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Tree BFS Level Order Traversal in Go
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}
    head := 0 // Efficient head pointer instead of re-slicing array!

    for head < len(queue) {
        levelSize := len(queue) - head // CRUCIAL: Snapshot queue size before processing level!
        currentLevel := make([]int, 0, levelSize)

        for i := 0; i < levelSize; i++ {
            node := queue[head]
            head++

            currentLevel = append(currentLevel, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, currentLevel)
    }

    return result
}

The Golden Rule: Snapshot levelSize BEFORE the Loop

// Minimum Depth of Binary Tree using BFS (Early Stop!)
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    queue := []*TreeNode{root}
    depth := 1

    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            // First leaf encountered in BFS is automatically at minimum depth!
            if node.Left == nil && node.Right == nil {
                return depth
            }

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        depth++
    }
    return depth
}

BFS vs DFS Comparison

LEVEL / NEAREST → Use Tree BFS (Queue FIFO)
PATH / SUBTREE  → Use Tree DFS (Recursion)
levelSize       → Snapshot len(queue) BEFORE inner loop
Min Depth       → BFS early stop on first leaf node
Right Side View → Take last element of each level slice

Common Interview Mistakes

Interview Rules

1. 1. Level by level traversal? → Tree BFS
2. 2. Queue structure? → FIFO (First In First Out)
3. 3. Level slice separation? → Snapshot levelSize = len(queue) before inner loop
4. 4. Minimum depth / nearest level? → BFS early stop on first leaf node
5. 5. Right side view? → Append last node of each level slice (i == levelSize - 1)
6. 6. Bottom left value? → First node of deepest level slice (i == 0)
7. 7. Zigzag order? → BFS + direction flag toggle (leftToRight = !leftToRight)
8. 8. Overall Complexity → Time: O(N) | Queue Space: O(W) where W is maximum tree width (O(N) worst case)

Tree BFS        → Queue FIFO
Level Order     → levelSize
Process         → Current level only
Children        → Next level
Minimum depth   → First leaf found
Right side view → Last node
Bottom left     → First node
Zigzag          → Alternate direction
Time            → O(N)
Space           → O(Width)

💡 Golden Rule: "Snapshot the current queue size, process exactly that many nodes, and everything you add belongs to the next level."