Start learning free

LESSON 310 OF 347 · BINARY TREES

Level Order Traversal in C#: DFS with a Level Index

Practice O(n) Read the full explanation

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

Example:

Input: [3, 9, 20, null, null, 15, 7]
    3
   / \
  9  20
    /  \
   15   7

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

STEP 1 OF 9
    Ctrl + Enter to check

    C# · BINARY TREES

    Level Order Traversal in C#, explained

    Problem overview

    The method levelOrderTraversal receives the root of a binary tree and returns a List<List<int>>. Each inner list holds the values of one level of the tree, from left to right, and the inner lists go from the top level down.

    In the example, the tree has 3 at the root, 9 and 20 below it, and 15 and 7 under 20. The result is [[3], [9, 20], [15, 7]]. An empty tree (a null root) gives an empty outer list.

    Approach: depth-first search that remembers the level

    Level order is usually taught with a queue and a breadth-first search. This lesson does the same job with plain recursion. The idea: the outer list is indexed by level, so result[level] is the list for that level. If every node knows its own depth, it can append its value to the right inner list no matter when the recursion reaches it.

    Two facts make that work:

    • The root is on level 0, and a child is always one level deeper than its parent, so the recursive call passes level + 1.
    • If the recursion visits the left subtree before the right subtree, then within any single level the values are appended in left-to-right order. A node further left on a level is always reached before a node further right on the same level.

    The only open question is when to create an inner list. The first time the recursion reaches a new depth, level equals result.Count, which means the list for that level doesn't exist yet. Because the search only ever goes one level deeper than it has been before, a single Add is enough to make it exist.

    Step by step

    1. Create the result. An empty List<List<int>> named result collects everything.
    2. Delegate to a helper. Dfs(root, 0, result) fills result for the whole tree, starting at level 0.
    3. Return result.
    4. Declare the helper. Dfs returns nothing (void) and takes the node, its level and the shared result. It writes into the list the caller gave it, so there is nothing to return.
    5. Stop at null. An empty subtree has no values, so the method returns at once. This is also what ends the recursion below the leaves.
    6. Add a level when needed. If level >= result.Count, this is the first node seen on that level, so an empty inner list is added.
    7. Record the value in result[level].
    8. Recurse left with level + 1.
    9. Recurse right with level + 1.

    The solution in C#

    class Solution {

    public void Dfs(TreeNode root, int level, List<List<int>> result) {
        if (root == null) {
            return;
        }
        if (level >= result.Count) {
            result.Add(new());
        }
        result[level].Add(root.val);
        Dfs(root.left, level + 1, result);
        Dfs(root.right, level + 1, result);
    }

    public List<List<int>> levelOrderTraversal(TreeNode root) {
        List<List<int>> result = new List<List<int>>();
        Dfs(root, 0, result);
        return result;
    }
}

    C# details worth knowing:

    • Target-typed new(). In result.Add(new()) the compiler knows Add expects a List<int>, so new() creates exactly that. It is shorthand for new List<int>() and needs C# 9 or later.
    • Lists are reference types. The caller and Dfs hold references to the same List object, so every Add inside the recursion is visible in levelOrderTraversal. That is why Dfs can be void and no ref is needed.
    • Indexing a list. result[level] reads the inner list at that position, and .Add(root.val) appends to it. An index that is out of range throws ArgumentOutOfRangeException, which is why the level must be created first.
    • Names. The lesson's method is levelOrderTraversal, starting with a lowercase letter, and the fields are val, left and right. C# is case-sensitive, so keep them exactly as given. Many C# programs use PascalCase for method names, but a call to LevelOrderTraversal wouldn't find this method.

    Complexity

    Time: O(n). Every node is visited exactly once, and each visit does constant work: one comparison, at most one Add of an empty list, and one Add of a value.

    Space: O(n). The result holds all n values. On top of that, the recursion uses stack space proportional to the height of the tree: O(log n) for a balanced tree and O(n) for one that leans entirely to one side. A queue-based breadth-first search has the same time and also uses O(n) space.

    Edge cases and common mistakes

    • Empty tree. With a null root, Dfs returns immediately and the method returns an empty list, not null.
    • Single node. The result is [[5]] for a tree holding just 5.
    • Skewed tree. A tree where each node has only a right child gives one value per level, such as [[1], [2], [3]].
    • Visiting right before left. The levels would come out right to left. Keep the left call first.
    • Using level > result.Count. That never creates the first list, because on level 0 with an empty result the condition is false, and result[0] then throws.
    • Creating a list on every visit. That would give each node its own list and lose the grouping. The new list is added only when the level is new.
    • Forgetting the null check. Reading root.val on a null node throws NullReferenceException.

    Testing

    • The tree [3, 9, 20, null, null, 15, 7] gives [[3], [9, 20], [15, 7]].
    • A tree with only the root 1 gives [[1]].
    • A null root gives [].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free