Level Order Traversal (102. Binary Tree Level Order Traversal)

Given a binary tree, return the level order traversal of its nodes' values.

Example:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output:
[
  [3],
  [9,20],
  [15,7]
]

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Approach: We can solve this problem using a breadth-first search (BFS) approach. We'll use a queue to store nodes at each level and process them level by level.

Algorithm:

  • Create an empty result list res to store the level order traversal.
  • Create a queue q and enqueue the root node.
  • While the queue is not empty:
    • a. Dequeue all nodes at the current level and store their values in a temporary list level.
    • b. Add level to the result list res.
    • c. Enqueue all children of the nodes at the current level.
  • Return the result list res.

Code:

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


func levelOrder(root *TreeNode) [][]int {
	 if root == nil {
	 	return [][]int{}
	 }
     
	 var result [][]int
	 var queue = []*TreeNode{root}
	 for len(queue) > 0 {
     
	 	size := len(queue)
	 	var level []int
	 	for i := 0; i < size; i++ {
	 		node := queue[i]
	 		level = append(level, node.Val)
	 		if node.Left != nil {
	 			queue = append(queue, node.Left)
	 		}
	 		if node.Right != nil {
	 			queue = append(queue, node.Right)
	 		}
	 	}
	 	queue = queue[size:]
	 	result = append(result, level)
	 }
	 return result
}