102.binary-tree-level-order-traversal.md

102. Binary Tree Level Order Traversal

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
      1
     /  \
    2    3
   /    / \
  5    9   7
Output: [[1], [2, 3], [5, 9, 7]]

Edge / Corner Cases

• Empty tree

Input: 
Output: [] 

• Single node

Input: 1
Output: [[1]]

• Skewed tree

Input: 
      1
       \
        2
         \
          3
Output: [[1], [2], [3]]

Iterative

fun levelOrder(root: TreeNode?): List<List<Int>> {
    if (root == null) return emptyList()
    val results = mutableListOf<List<Int>>()
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    while (!queue.isEmpty()) {
        val levelNodes = mutableListOf<Int>()
        // The items in queue now are at the same level.
        // We iterate the all nodes now for same level.
        val size = queue.size
        for (i in 0 until size) {
            val node = queue.removeFirst()
            levelNodes.add(node.`val`)
            if (node?.left != null) queue.addLast(node.left!!)
            if (node?.right != null) queue.addLast(node.right!!)
        }
        results.add(levelNodes)
    }
    return results
}

Recursive

We maintain the values of each level, and dfs by tracking the level of the node.

val results = mutableListOf<MutableList<Int>>()
    
fun levelOrder(root: TreeNode?): List<List<Int>> {
    dfs(root, 0)
    return results
}

private fun dfs(root: TreeNode?, level: Int) {
    if (root == null) return
    val nodes = results.getOrNull(level)
    if (nodes == null) {
        val list = mutableListOf<Int>()
        list.add(root.`val`)
        results.add(list)
    } else {
        results[level].add(root.`val`)
    }
    dfs(root.left, level + 1)
    dfs(root.right, level + 1)
}

• Time Complexity: O(n).
• Space Complexity: O(n).