Skip to content

102 Binary Tree Level Order Traversal ✅

Leetcode

Use List<List<int>>() to track level values

::: tip Key Points

  • queue
  • Use Null (a special element) to divide each layer in the queue
  • Basic tree BFS
  • Note that when inserting null, check where the current queue is empty, otherwise it will loop indefinitely :::

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: alt

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

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

C# Solution

using System;
using System.Collections.Generic;
// using System.Linq;

namespace Algorithms.Medium
{
  /*
  public class TreeNode
  {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
  }
  */

  public class BinaryTreeLevelOrderTraversal
  {
    public static List<IList<int>> LevelOrder(TreeNode root)
    {
      var levels = new List<IList<int>>();
      if (root == null) return levels;

      var queue = new Queue<TreeNode>();
      queue.Enqueue(root);

      var levelIndex = 0;

      while (queue.Count > 0)
      {
        levels.Add(new List<int>());

        var queueCount = queue.Count;
        for (var i = 0; i < queueCount; i++)
        {
          TreeNode currentNode = queue.Dequeue();

          // levels.ElementAt(level).Add(currentNode.val);
          levels[levelIndex].Add(currentNode.val);

          if (currentNode.left != null) queue.Enqueue(currentNode.left);
          if (currentNode.right != null) queue.Enqueue(currentNode.right);
        }

        levelIndex++;
      }

      return levels;
    }
  }
}

C# Tests

using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class BinaryTreeLevelOrderTraversalTests
  {
    [Fact]
    public void LevelOrderTest()
    {
      TreeNode l0 = new TreeNode(3);
      l0.left = new TreeNode(9);
      l0.right = new TreeNode(20);
      l0.right.left = new TreeNode(15);
      l0.right.right = new TreeNode(7);

      var expectedLevels = new List<List<int>>();
      expectedLevels.Add(new List<int> { 3 });
      expectedLevels.Add(new List<int> { 9, 20 });
      expectedLevels.Add(new List<int> { 15, 7 });

      Assert.Equal(expectedLevels, BinaryTreeLevelOrderTraversal.LevelOrder(l0));
    }
  }
}

Variant: 107. Binary Tree Level Order Traversal II Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]

Other BFS problems