Breadth First Search

This technique uses recursion or iterative approach using queue to traverse of a tree in a level-by-level order. A queue keeps track of all the nodes of a level before jumping onto the next level.

How to Identify

• Data Structure Involves: Tree, Graph
• Question Type: Traverse a tree in a level-by-level order.

Example

Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Recursive

levelOrder.ts

import {TreeNode} from "./TreeNode"
function levelOrder(root: TreeNode | null): number[][] {
  const levels: number[][] = []
  
  function helper(root: TreeNode | null, level: number) {
    if(root === null) return
    if(levels.length === level) levels[level] = []
    
    levels[level].push(root.val)
    helper(root.left, level+1)
    helper(root.right, level+1)
  }
    
  helper(root, 0)
  return levels
}

Iterative

levelOrder.ts

import {TreeNode} from "./TreeNode"
function levelOrderIterative(root: TreeNode | null): number[][] {
  if(root === null) return []
  
  const queue = [root]
  const levels: number[][] = []
  
  while(queue.length > 0) {
    const len = queue.length
    const level: number[] = []
    
    for(let i=0; i<len; i++){
      const current = queue.shift()
      level.push(current.val)
      if(current.left) queue.push(current.left)
      if(current.right) queue.push(current.right)
    }
    
    levels.push(level)
  }
  
  return levels
}

TreeNode

TreeNode.ts

export class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
    
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
  }
}

Related Problems

	Problems	Difficulty
1	Binary Tree Level Order Traversal	Medium
2	Binary Tree Zigzag Level Order Traversal	Medium