Binary Tree Level Order Traversal

1. Problem Description

Given a binary tree, return the node values obtained by level-order traversal (that is, visit all nodes level by level from left to right).

2. Approach

1. Approach 1
   • Level-order traversal visits the tree one level at a time
   • It is essentially BFS, and BFS uses a queue
   • Level-order traversal needs to know when the current level is finished, so a variable records the last node of the current level;
   • Another variable records the last node of the next level so that the marker can be updated
2. Approach 2
   • Level-order traversal visits the tree one level at a time
   • It is essentially BFS, and BFS uses a queue
   • Before traversing each level, record the number of nodes n currently in the queue (the number of nodes in this level), then process all n nodes at once

3. Implementation

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }


    allPaths := make([][]int, 0)
    path := make([]int, 0)
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    currentLineLast := root
    var nextLineLast *TreeNode
    for len(queue) > 0 {
        root := queue[0]
        queue = queue[1:]

        path = append(path, root.Val)
        if root.Left != nil {
            queue = append(queue, root.Left)
            nextLineLast = root.Left
        }
        if root.Right != nil {
            queue = append(queue, root.Right)
            nextLineLast = root.Right
        }

        if root == currentLineLast {
            allPaths = append(allPaths, path)
            path = make([]int, 0)
            currentLineLast = nextLineLast
        }
    }


    return allPaths

}

4. References

• BFS Use Cases: Level-Order Traversal and Shortest Paths - LeetCode