Level Order Traversal of a Binary Tree using Iteration

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given a binary tree, perform a level order traversal (also known as breadth-first traversal) using an iterative approach. In this traversal, nodes are visited level by level from left to right. Return a list of values grouped by each level.

Examples❯

Input Tree Level Order Output Description
[1, 2, 3, 4, 5, null, 6]
[[1], [2, 3], [4, 5, 6]] Standard case: Tree with three levels and missing left/right children
[1]
[[1]] Edge case: Tree with a single node (root only)
[] [] Edge case: Empty tree (no nodes at all)
[1, 2, null, 3, null, null, null, 4]
[[1], [2], [3], [4]] Edge case: Tree skewed to the left only
[1, null, 2, null, null, null, 3]
[[1], [2], [3]] Edge case: Tree skewed to the right only

Visualization Player

Solution❯

Case 1: Standard Binary Tree

In a normal binary tree with both left and right children, level order traversal means we start at the root, then move to the second level, then third, and so on, from left to right. We use a queue to store nodes as we traverse each level. For instance, in the tree [1, 2, 3, 4, 5, null, 6], we first visit 1, then 2 and 3, then 4, 5, and 6, maintaining the left-to-right order.

Case 2: Single Node Tree

In this case, the tree only contains the root node. There are no children to traverse, so the output will simply be a single level containing just the root value. For example, [1] → [[1]].

Case 3: Empty Tree

If the input is an empty array (i.e., the root node is null), then there's nothing to traverse. Hence, we directly return an empty list []. This is a common edge case and should be handled at the start of the function.

Case 4: Left-Skewed Tree

In a left-skewed tree, each node only has a left child. The traversal in such a case will yield one node at each level in top-down order. For instance, [1, 2, null, 3, null, 4] results in [[1], [2], [3], [4]].

Case 5: Right-Skewed Tree

Similarly, a right-skewed tree where each node only has a right child will also produce one node per level. For example, [1, null, 2, null, 3, null, 4] gives [[1], [2], [3], [4]].

By covering all these scenarios, a beginner can understand how breadth-first traversal adapts to different binary tree shapes and how using a queue helps ensure each level is processed correctly.

Algorithm Steps❯

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Initialize a queue and enqueue the root node.
  4. While the queue is not empty, dequeue a node, record its value, and enqueue its left and right children (if they exist).
  5. Continue until the queue is empty; the recorded values represent the level order traversal.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrderTraversal(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(levelOrderTraversal(root))