Level Order Traversal of a Binary Tree using Recursion

Problem Statement❯

Given a binary tree, perform a level order traversal using a recursive approach. In level order traversal, nodes are visited level by level from left to right. Return the result as a list of levels, where each level is a list of node values.

Examples❯

Binary Tree (Level-Order)	Output	Description
[1, 2, 3, 4, 5, null, 6]	[[1], [2, 3], [4, 5, 6]]	Normal binary tree with multiple levels and both left-right children
[10, null, 20, null, null, null, 30]	[[10], [20], [30]]	Right-skewed binary tree (each node has only right child)
[5, 3, null, 1]	[[5], [3], [1]]	Left-skewed binary tree (each node has only left child)
[]	[]	Empty tree (no nodes present)
[42]	[[42]]	Single-node tree

Visualization Player

Solution❯

Case 1: Normal Binary Tree

In a normal binary tree with both left and right children at various levels, the recursive level order traversal works by computing the tree's height and then collecting nodes at each level. For example, for a tree with root 1, children 2 and 3, and grandchildren 4, 5, and 6, we process level 1 with node 1, level 2 with nodes 2 and 3, and level 3 with nodes 4, 5, and 6.

Case 2: Right-Skewed Tree

Here, each node has only a right child. The traversal will go one node at each level, moving down the right children. So the traversal looks like: level 1 → 10, level 2 → 20, level 3 → 30. The recursive function handles each level separately, and although there's no left child, the right child still triggers the recursion for deeper levels.

Case 3: Left-Skewed Tree

Similar to the right-skewed case, but now each node only has a left child. The recursive function will only recurse into the left subtree. For a tree with nodes 5 → 3 → 1, the traversal results in level 1 → 5, level 2 → 3, level 3 → 1.

Case 4: Empty Tree

If the tree is empty (root is null), there are no nodes to process. The function should check for this at the start and return an empty list immediately. This prevents unnecessary computation or recursive calls.

Case 5: Single Node Tree

With just one node in the tree (say, root = 42), the level order traversal simply returns a single level with that node: [[42]]. Even though it has no children, the base condition of recursion will include this node and stop further processing.

Algorithm Steps❯

Find the height of the binary tree.
For each level from 1 to height, recursively traverse the tree to collect nodes at that level.
The recursive function printLevel checks if the current level is 1; if so, it records the node's value, otherwise it recurses on the left and right children with level-1.
Concatenate the nodes from each level to produce the level order traversal.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

def printLevel(root, level, result):
    if not root:
        return
    if level == 1:
        result.append(root.val)
    elif level > 1:
        printLevel(root.left, level - 1, result)
        printLevel(root.right, level - 1, result)

def levelOrderTraversal(root):
    h = height(root)
    result = []
    for i in range(1, h + 1):
        printLevel(root, i, result)
    return result

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(levelOrderTraversal(root))

⬅ Previous TopicPostorder Traversal of a Binary Tree using Iteration

Next Topic ⮕Level Order Traversal of a Binary Tree using Iteration