Solutions

1. Breadth First Search

O(n) time | O(n) space

Intuition

We can traverse through the tree with a queue, putting the children of every node we take back into it, so the nodes come out level by level.

Algorithm

Return an empty array if the tree is empty.
Create an empty array for the answer and a queue with the root in it.
Traverse through the tree while the queue has nodes to take.
- Create an empty array for the current level.
- Take as many nodes as the queue holds now, adding the value of every node taken to the current level array and putting its children into the queue.
- Add the current level array to the answer.
Return the answer.

take 3, put 9 and 20 on the queue

1 / 7

Code

# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    levels = []
    queue = [root]
    front = 0
    while front < len(queue):
        level = []
        back = len(queue)
        while front < back:
            node = queue[front]
            front += 1
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return []
  const levels = []
  const queue = [root]
  let front = 0
  while (front < queue.length) {
    const level = []
    const back = queue.length
    while (front < back) {
      const node = queue[front]
      front += 1
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    levels.push(level)
  }
  return levels
}

// Definitions:
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//
//     TreeNode() {}
//
//     TreeNode(int val) {
//         this.val = val;
//     }
//
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int wide = queue.size();
            for (int i = 0; i < wide; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(level);
        }
        return levels;
    }
}

2. Depth First Search

O(n) time | O(n) space

Intuition

We can traverse through the tree carrying the depth of every node we pass, which is the level that node belongs to.

Algorithm

Create an empty array for the answer.
Traverse through the tree from the root with a depth variable starting at 0.
Add an empty array to the answer if it holds none for this depth yet.
Add the node value to the array at this depth.
Repeat the same for the left child and then the right child, with depth increased by one.
Return the answer.

take 3 at depth 0

1 / 7

Code

Recursive implementation

Code

# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:
    levels = []
    dfs(root, 0, levels)
    return levels


def dfs(node: TreeNode, depth: int, levels: list[list[int]]) -> None:
    if not node:
        return
    if depth == len(levels):
        levels.append([])
    levels[depth].append(node.val)
    dfs(node.left, depth + 1, levels)
    dfs(node.right, depth + 1, levels)

// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {number[][]}
 */
var levelOrder = function (root) {
  const levels = []
  dfs(root, 0, levels)
  return levels
}

function dfs(node, depth, levels) {
  if (!node) return
  if (depth === levels.length) levels.push([])
  levels[depth].push(node.val)
  dfs(node.left, depth + 1, levels)
  dfs(node.right, depth + 1, levels)
}

// Definitions:
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//
//     TreeNode() {}
//
//     TreeNode(int val) {
//         this.val = val;
//     }
//
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        dfs(root, 0, levels);
        return levels;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> levels) {
        if (node == null) return;
        if (depth == levels.size()) levels.add(new ArrayList<>());
        levels.get(depth).add(node.val);
        dfs(node.left, depth + 1, levels);
        dfs(node.right, depth + 1, levels);
    }
}

Iterative implementation

Code

# Definitions:
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:
    levels = []
    stack = [(root, 0)]
    while stack:
        node, depth = stack.pop()
        if not node:
            continue
        if depth == len(levels):
            levels.append([])
        levels[depth].append(node.val)
        stack.append((node.right, depth + 1))
        stack.append((node.left, depth + 1))
    return levels

// Definitions:
// function TreeNode(val, left, right) {
//     this.val = val === undefined ? 0 : val
//     this.left = left === undefined ? null : left
//     this.right = right === undefined ? null : right
// }

/**
 * @param {TreeNode} root
 * @returns {number[][]}
 */
var levelOrder = function (root) {
  const levels = []
  const stack = [[root, 0]]
  while (stack.length) {
    const [node, depth] = stack.pop()
    if (!node) continue
    if (depth === levels.length) levels.push([])
    levels[depth].push(node.val)
    stack.push([node.right, depth + 1])
    stack.push([node.left, depth + 1])
  }
  return levels
}

// Definitions:
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//
//     TreeNode() {}
//
//     TreeNode(int val) {
//         this.val = val;
//     }
//
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    private record Step(TreeNode node, int depth) {}

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        Deque<Step> stack = new ArrayDeque<>();
        stack.push(new Step(root, 0));
        while (!stack.isEmpty()) {
            Step at = stack.pop();
            if (at.node() == null) continue;
            if (at.depth() == levels.size()) levels.add(new ArrayList<>());
            levels.get(at.depth()).add(at.node().val);
            stack.push(new Step(at.node().right, at.depth() + 1));
            stack.push(new Step(at.node().left, at.depth() + 1));
        }
        return levels;
    }
}