Level order traversal of a binary tree

Given a binary tree, return level order traversal

Example

Output: [[1], [5, 3]]

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/

public sealed class Solution
{
    public List<List<int>> LevelOrder(TreeNode root)
    {
    }
}

Algorithm

We already know how to traverse a binary, the only difference is to traverse by level. During the traversal, we need to store a level of a node. The easiest way to do it is to use recursion.

To solve this problem we can use Preorder traversal algorithm because as per the problem we need to visit left subtree first.

The Preorder algorithm does exactly what we want

• Visit the root
• Visit the left subtree
• Visit the right subtree

    public void PreorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        Console.WriteLine(root.Value);
        PreorderTraversal(root.Left);
        PreorderTraversal(root.Right);
    }

So, we have a traversal algorithm and the only thing left is to store a node level. We can do it by adding an additional parameter in our recursion call.

Code:

public List<List<int>> LevelOrder(TreeNode root)
{
    if (root == null)
    {
        return new List<List<int>>();
    }

    var result = new List<List<int>>();
    LevelOrder(root, 0, result);
    return result;
}

private static void LevelOrder(TreeNode root, int level, List<List<int>> result)
{
    if (root == null)
    {
        return;
    }

    if (level >= result.Count)
    {
        result.Add(new List<int>());
    }

    result[level].Add(root.Value);

    LevelOrder(root.Left, level + 1, result);
    LevelOrder(root.Right, level + 1, result);
}

Time Complexity: O(n)

Video Lesson