ProgramGuru

Level Order Traversal of a Binary Tree using Recursion

Problem and examples

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.
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
"

Explore Level Order Traversal of a Binary Tree - Recursion

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};

int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

void printLevel(TreeNode* root, int level) {
    if (!root) return;
    if (level == 1) cout << 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 = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    levelOrder(root);
    return 0;
}

Python implementation

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

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

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    public static int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public static void printLevel(TreeNode root, int level) {
        if (root == null) return;
        if (level == 1) System.out.print(root.val + " ");
        else {
            printLevel(root.left, level - 1);
            printLevel(root.right, level - 1);
        }
    }

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        levelOrder(root);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function height(root) {
    if (!root) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

function printLevel(root, level, result) {
    if (!root) return;
    if (level === 1) result.push(root.val);
    else {
        printLevel(root.left, level - 1, result);
        printLevel(root.right, level - 1, result);
    }
}

function levelOrderTraversal(root) {
    const h = height(root);
    let result = [];
    for (let i = 1; i <= h; i++) {
        printLevel(root, i, result);
    }
    return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(levelOrderTraversal(root));

Go implementation

package main
import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    l := height(root.left)
    r := height(root.right)
    if l > r {
        return l + 1
    }
    return r + 1
}

func printLevel(root *TreeNode, level int) {
    if root == nil {
        return
    }
    if level == 1 {
        fmt.Print(root.val, " ")
    } else {
        printLevel(root.left, level-1)
        printLevel(root.right, level-1)
    }
}

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

func main() {
    root := &TreeNode{1, nil, nil}
    root.left = &TreeNode{2, nil, nil}
    root.right = &TreeNode{3, nil, nil}
    root.left.left = &TreeNode{4, nil, nil}
    root.left.right = &TreeNode{5, nil, nil}
    levelOrder(root)
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn height(node: &Option<Box<TreeNode>>) -> i32 {
    match node {
        Some(n) => 1 + height(&n.left).max(height(&n.right)),
        None => 0,
    }
}

fn print_level(node: &Option<Box<TreeNode>>, level: i32) {
    if let Some(n) = node {
        if level == 1 {
            print!("{} ", n.val);
        } else if level > 1 {
            print_level(&n.left, level - 1);
            print_level(&n.right, level - 1);
        }
    }
}

fn level_order(root: &Option<Box<TreeNode>>) {
    let h = height(root);
    for i in 1..=h {
        print_level(root, i);
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode::new(4))),
            right: Some(Box::new(TreeNode::new(5))),
        })),
        right: Some(Box::new(TreeNode::new(3))),
    }));

    level_order(&root);
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun height(root: TreeNode?): Int {
    if (root == null) return 0
    return 1 + maxOf(height(root.left), height(root.right))
}

fun printLevel(root: TreeNode?, level: Int) {
    if (root == null) return
    if (level == 1) print("${root.value} ")
    else {
        printLevel(root.left, level - 1)
        printLevel(root.right, level - 1)
    }
}

fun levelOrder(root: TreeNode?) {
    val h = height(root)
    for (i in 1..h) {
        printLevel(root, i)
    }
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left?.left = TreeNode(4)
    root.left?.right = TreeNode(5)
    levelOrder(root)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func height(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    return 1 + max(height(root.left), height(root.right))
}

func printLevel(_ root: TreeNode?, _ level: Int) {
    guard let root = root else { return }
    if level == 1 {
        print("\(root.val)", terminator: " ")
    } else {
        printLevel(root.left, level - 1)
        printLevel(root.right, level - 1)
    }
}

func levelOrder(_ root: TreeNode?) {
    let h = height(root)
    for i in 1...h {
        printLevel(root, i)
    }
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
levelOrder(root)

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function height(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

function printLevel(root: TreeNode | null, level: number, result: number[]): void {
    if (!root) return;
    if (level === 1) result.push(root.val);
    else {
        printLevel(root.left, level - 1, result);
        printLevel(root.right, level - 1, result);
    }
}

function levelOrderTraversal(root: TreeNode | null): number[] {
    const h = height(root);
    const result: number[] = [];
    for (let i = 1; i <= h; i++) {
        printLevel(root, i, result);
    }
    return result;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3));
console.log(levelOrderTraversal(root));