LeetCode Meditations: Binary Tree Level Order Traversal

Let's start with the description for 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:

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

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. In this problem, we only need to get the values of the nodes in each level.

My initial solution in TypeScript looked like this:

/**
 * 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;
}

/**
 * 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 $O(n)$ as we visit each node once in the tree. Since the largest level in a binary tree can be of length $\frac{n + 1}{2}$ where $n$ is the total number of nodes in the tree, the space complexity also ends up being $O(n)$ as we store each level.

Similar to the version above, another solution might look like this (as in this example by NeetCode) — let's see it in Python this time:

# 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

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

/**
 * 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;
}

/**
 * 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;
}

The time and space complexity are the same for this solution as well, that is, both are $O(n)$ .

Next up, we'll validate a binary search tree in the problem with the appropriate title, Validate Binary Search Tree. Until then, happy coding.

Eda Eren

LeetCode Meditations: Binary Tree Level Order Traversal

Time and space complexity