Level Order Traversal of a Binary Tree - Recursion - Visualization

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

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
"

Solution❯

Understanding the Problem

Level Order Traversal of a Binary Tree means visiting all nodes level by level, from left to right. Unlike in-order, pre-order, or post-order traversals that go deep into subtrees first, level order processes nodes horizontally. Traditionally, level order traversal is done using a queue (i.e., iteratively), but here we are solving it recursively.

The challenge in recursion is that we don’t have an implicit queue. So, we need to first understand how to recursively process each level, one by one.

Step-by-Step Solution with Example

Step 1: Understand Tree Height

To process each level individually, we need to know how many levels (or height) the tree has. We compute the height by recursively checking the maximum depth of left and right subtrees.

Step 2: Collect Nodes at Each Level

Once we know the height of the tree (say H), we run a loop from level 1 to level H. For each level, we use a helper function that collects all nodes at that level using recursion. This function takes the current node and the level to target.

Step 3: Process Example Tree

Let’s take an example tree:


       1
     /       2     3
   /        4   5     6

Level 1: Node 1
Level 2: Nodes 2, 3
Level 3: Nodes 4, 5, 6

The height of the tree is 3. For each level from 1 to 3, we collect nodes recursively.

Step 4: Recursive Helper Logic

The helper function works as follows:

  • If level is 1, push the node’s value into the result list.
  • If level > 1, recursively call the function on left and right children with level - 1.
This way, we traverse each level separately using recursive depth control.

Edge Cases

Case 1: Right-Skewed Tree

Every node has only a right child: 


   10
          20
              30
Each level contains one node, and the recursion moves down the right subtree only. The traversal is: [[10], [20], [30]].

Case 2: Left-Skewed Tree

Every node has only a left child: 


    5
   /
  3
 /
1
The recursion will only follow the left children: [[5], [3], [1]].

Case 3: Empty Tree

If the root is null, return an empty list. Always check for this at the beginning to avoid unnecessary calls.

Case 4: Single Node Tree

If the tree has only one node, e.g., root = 42, we return [[42]]. This is a valid level with just one node.

Finally

Level Order Traversal using recursion is a powerful way to think in terms of depth and breadth together. It challenges the usual approach and teaches us to simulate level-based logic using recursive depth counters. Understanding the tree height and correctly processing each level separately is the key.

Always consider edge cases like empty trees, skewed structures, and minimal nodes while designing the solution. Once you master this pattern, you can apply it to more complex tree problems with confidence.

Algorithm Steps❯

  1. Find the height of the binary tree.
  2. For each level from 1 to height, recursively traverse the tree to collect nodes at that level.
  3. 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.
  4. Concatenate the nodes from each level to produce the level order traversal.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int height(TreeNode* root) {
    if (root == NULL) return 0;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

void printLevel(TreeNode* root, int level) {
    if (!root) return;
    if (level == 1) printf("%d ", root->val);
    else {
        printLevel(root->left, level - 1);
        printLevel(root->right, level - 1);
    }
}

void levelOrder(TreeNode* root) {
    int h = height(root);
    for (int i = 1; i <= h; i++) {
        printLevel(root, i);
    }
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    levelOrder(root);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...