LESSON 311 OF 348 · BINARY TREES

Level Order Traversal in TypeScript: DFS with a Level Index

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

Guided

Ctrl + Enter to check

TYPESCRIPT · BINARY TREES

Level Order Traversal in TypeScript, explained

Problem overview

The method levelOrderTraversal receives the root of a binary tree and returns a number[][]: one inner array per level, from the root down, each listing its values from left to right.

In the example, 3 is the root. Its children are 9 and 20, and 20 has children 15 and 7. The levels are therefore [3], [9, 20] and [15, 7], and the answer is [[3], [9, 20], [15, 7]]. An empty tree has no levels, so the answer is [].

Approach: a depth-first search that knows its depth

The usual way to go level by level is a queue (breadth-first search). This lesson takes another route that needs no queue: an ordinary recursive traversal that carries the current level as an argument. The root is level 0 and a child is always one level deeper than its parent.

The result is an array of arrays, and result[level] collects the values of that level. The traversal visits the left subtree before the right one, so the values of any one level arrive from left to right. Two nodes on the same level are always separated by a branch point, and the left branch is explored completely first.

The only bookkeeping is creating the inner array when the traversal reaches a level for the first time. Because the search goes depth first, the first node ever seen on a new level is the leftmost one on it, and levels are discovered in increasing order, so a level is new exactly when level >= result.length.

Step by step

Declare result as a const of type number[][], initialised to an empty array.
Call the helper this.dfs with the root, level 0 and result. This is written before the helper exists: assume it fills result with the traversal of whatever subtree it receives.
Return result.
Declare dfs above the main method. It takes root (TreeNode | null), level (number) and result (number[][]), and returns void.
Stop on a missing node. A null child adds nothing, so return.
Open a new level if needed. When level >= result.length, no node has been seen this deep yet, so push an empty array.
Record the value by pushing root.val into result[level].
Recurse on the left child with level + 1.
Recurse on the right child with level + 1. The left-then-right order is what keeps each level sorted from left to right.

The solution in TypeScript

class Solution {

    dfs(root: TreeNode | null, level: number, result: number[][]): void {
        if (!root) {
            return;
        }
        if (level >= result.length) {
            result.push([]);
        }
        result[level].push(root.val);
        this.dfs(root.left, level + 1, result);
        this.dfs(root.right, level + 1, result);
    }

    levelOrderTraversal(root: TreeNode | null): number[][] {
        const result: number[][] = [];
        this.dfs(root, 0, result);
        return result;
    }
}

TypeScript details worth knowing:

number[][] is an array of number arrays. result.push([]) adds a new empty inner array, and result[level].push(root.val) then reaches into it. The empty literal [] is accepted there because the compiler already knows what result holds.
result[level] always exists at that line. The earlier if guarantees it: levels are opened in order, so when level is at most result.length - 1 the inner array is already there. The compiler can't verify that from the types, so it relies on you.
Shared array. const only stops result from being reassigned. All the recursive calls push into the one array the caller created.
Methods are reached through this. A bare dfs(...) inside the class would not find the method.

Complexity

Time: O(n). Every node is visited once, and each visit does a comparison and a push, both constant time on average.

Space: O(n). The output holds every value once. On top of that, the recursion uses O(h) stack frames, where h is the height of the tree. For a tree that is a single long chain, h is n, and a very deep chain can exhaust the call stack. A queue-based version has no such limit.

Edge cases and common mistakes

An empty tree. The first call returns at once and the result is [], not [[]].
A lopsided tree. Take root 1 with left child 2 and right child 3, where 2 has only a right child 4. The answer is [[1], [2, 3], [4]]. The search reaches 4 before it reaches 3, but 4 is filed under level 2 and 3 under level 1, so level 1 still ends up as [2, 3].
Checking level === result.length instead of >=. It also works here, because levels are opened one at a time, but >= says directly what is meant: "deeper than anything seen so far".
Forgetting the new inner array. Without the push([]), result[level] is undefined and calling push on it throws a TypeError.
Visiting the right child first. Every level would come out reversed.
Passing level instead of level + 1. Every node would be filed under the same level.

Testing

The example tree gives [[3], [9, 20], [15, 7]].
An empty tree gives [].
A single node with value 5 gives [[5]].
Root 1, left child 2 (with right child 4) and right child 3 give [[1], [2, 3], [4]].

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free