LeetCode Meditations: Binary Tree Level Order Traversal
Tags: computerscience, algorithms, python, typescript
Published: 2024-04-24 14:54:55

Let's start with the description for [Binary Tree Level Order Traversal](https://leetcode.com/problems/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).

For example:

<img src="https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg" alt="Example image" />

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

---

Level-order traversal is another name for [breadth-first search](https://rivea0.github.io/blog/leetcode-meditations-chapter-7-trees#bfs). In this problem, we only need to get the values of the nodes in each level.

My initial solution in TypeScript looked like this:

```ts
/**
 * Definition for a binary tree node.
 * 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)
 *   }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) {
    return [];
  }

  let result = [];
  let currentLevel = [root];

  while (currentLevel.length > 0) {
    let nextLevel = [];
    for (let node of currentLevel) {
      if (node !== null && node.left !== null) {
        nextLevel.push(node.left);
      }
      if (node !== null && node.right !== null) {
        nextLevel.push(node.right);
      }
    }

    result.push(currentLevel.map(node => node.val));
    currentLevel = nextLevel;
  }

  return result;
}
```

What we do is, first, check if `root` is null — in that case, we immediately return an empty array.

Then, we initialize a `result` array and another array to hold the nodes in the current level (which initially only has `root`).

As we traverse the tree, we add the nodes in the next level — that is, the left and right children of the nodes in the current level we're looking at. Once we're done with the current level, we add the values in it to `result`, and go to the next level in the tree, doing the same thing until there are no nodes left to look at.

#### Time and space complexity

The time complexity is {% katex inline %} O(n) {% endkatex %} as we visit each node once in the tree. Since [the largest level in a binary tree can be of length {% katex inline %} \frac{n + 1}{2} {% endkatex %}](https://en.wikipedia.org/wiki/Binary_tree#Properties_of_binary_trees) where {% katex inline %} n {% endkatex %} is the total number of nodes in the tree, the space complexity also ends up being {% katex inline %} O(n) {% endkatex %} as we store each level.

---

Similar to the version above, another solution might look like this (as in [this example by NeetCode](https://www.youtube.com/watch?v=6ZnyEApgFYg)) — let's see it in Python this time:

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    queue = collections.deque()
    queue.append(root)

    while queue:
        current_level = []
        current_queue_length = len(queue)
        for i in range(current_queue_length):
            node = queue.popleft()
            if node:
                current_level.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
        if current_level:
            result.append(current_level)
    
    return result
```

In this version, we use a [`deque`](https://docs.python.org/3/library/collections.html#collections.deque) for our queue. We initially append `root` to it, and as we traverse the tree, we append the values to `current_level`. Once we're done with a level, we append the values to `result`.

We can try a similar logic in TypeScript as well:

```ts
/**
 * Definition for a binary tree node.
 * 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)
 *   }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
  let result = [];
  let queue = [root];

  while (queue.length > 0) {
    let currentLevel = [];
    let currentQueueLength = queue.length;
    for (let i = 0; i < currentQueueLength; i++) {
      let node = queue.shift();
      if (node !== null) {
        currentLevel.push(node.val);
        queue.push(node.left);
        queue.push(node.right);
      }
    }
    if (currentLevel.length > 0) {
      result.push(currentLevel);
    }
  }
   
  return result;
}
```

| Note |
| :-- |
| We're keeping the length of `queue` in a separate variable called `currentQueueLength` — it's essentially needed to keep the levels separate. <br> (Note that we're mutating `queue`'s length inside the `for` loop with `queue.push` when we add the left and right children.) |

The time and space complexity are the same for this solution as well, that is, both are {% katex inline %} O(n) {% endkatex %}.
 
---

Next up, we'll validate a binary search tree in the problem with the appropriate title, [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree). Until then, happy coding.