ProgramGuru

Reverse Level Order Traversal of a Binary Tree using Recursion

Problem and examples

Given a binary tree, return the reverse level order traversal of its nodes’ values. In reverse level order traversal, we start from the bottom-most level and go up level by level, and within each level, nodes are visited from left to right. The traversal should be done using recursion only.
Input Tree Reverse Level Order Output Description
[1, 2, 3, 4, 5, null, 6] [[4, 5, 6], [2, 3], [1]] Standard tree with three levels and both 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] [[4], [3], [2], [1]] Left-skewed tree with increasing depth
[1, null, 2, null, null, null, 3] [[3], [2], [1]] Right-skewed tree with increasing depth
[7, 4, 9, 2, 5, 8, 10] [[2, 5, 8, 10], [4, 9], [7]] Complete binary tree with balanced left and right subtrees

Explore Reverse 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

We are given a binary tree and asked to perform a Reverse Level Order Traversal. This means we must visit nodes level by level, starting from the bottom-most level and moving upwards, while still visiting nodes from left to right within each level.

For example, in a normal level order traversal, we go from root to leaves: top to bottom. But in reverse level order traversal, we reverse this and go from bottom to top.

The twist here is that we need to solve it using recursion, which makes it more interesting than the iterative approach with a queue.

Step-by-Step Solution with Example

Step 1: Analyze the Given Tree

Let's consider a sample binary tree:


       1
      /      2   3
    /       4   5   6

The reverse level order traversal of this tree should return: [4, 5, 6, 2, 3, 1]

Step 2: Understand the Goal

We want to collect nodes level-by-level, but instead of printing levels immediately, we will store each level in a list. Once we collect all levels, we will reverse this list to simulate the bottom-to-top traversal.

Step 3: Calculate Tree Height

To traverse level-by-level recursively, we need to know how many levels there are. This can be done by computing the height of the tree first.

Step 4: Traverse and Collect Nodes Level-by-Level

We define a helper function that, given a level number, recursively collects all nodes at that level. We call this function for every level from 1 to the height of the tree and store each result in a list.

Step 5: Reverse the Levels

Once all levels are collected in order from top to bottom, we reverse the entire list of levels. This gives us bottom-to-top ordering.

Step 6: Flatten the Result

Finally, we combine all levels into one single flat list of node values. This will be our final reverse level order traversal.

Edge Cases

Case 1: Tree with Only One Node

If the tree has only the root node (e.g., 1), the output is simply [1]. There's no lower level to reverse, so it's just the root.

Case 2: Empty Tree

If the tree is null or empty, then there are no nodes to visit. The output should be an empty list: []. We must explicitly check for this to avoid null pointer errors during recursion.

Case 3: Skewed Tree (All Left or All Right)

Even if the tree is skewed (e.g., all left children or all right children), the process remains the same — collect level-by-level and reverse at the end.

Finally

This recursive solution builds a clean, structured approach to reverse level order traversal. It helps build an understanding of tree height, level-wise traversal using recursion, and managing order reversal through data structures. It’s beginner-friendly because it separates concerns: one function for height, another for collecting levels, and one final step to reverse and flatten the result.

Remember, recursion is powerful when the problem can be broken into smaller, repeatable tasks — and this problem is a great example of that.

  1. Traverse the binary tree recursively level by level starting from the root.
  2. For each level, record the nodes’ values in an auxiliary structure (e.g., an array or list).
  3. After the traversal, reverse the order of the recorded levels.
  4. Concatenate the values from the reversed levels to obtain the reverse level order traversal.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

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

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

void helper(TreeNode* node, int level, int levels[][100], int* levelSizes, int* maxLevel) {
    if (!node) return;
    if (level > *maxLevel) *maxLevel = level;
    levels[level][levelSizes[level]++] = node->val;
    helper(node->left, level + 1, levels, levelSizes, maxLevel);
    helper(node->right, level + 1, levels, levelSizes, maxLevel);
}

int* reverseLevelOrder(TreeNode* root, int* returnSize) {
    int levels[100][100];
    int levelSizes[100] = {0};
    int maxLevel = -1;
    helper(root, 0, levels, levelSizes, &maxLevel);
    int total = 0;
    for (int i = 0; i <= maxLevel; i++) total += levelSizes[i];
    int* result = malloc(total * sizeof(int));
    int index = 0;
    for (int i = maxLevel; i >= 0; i--) {
        for (int j = 0; j < levelSizes[i]; j++) {
            result[index++] = levels[i][j];
        }
    }
    *returnSize = total;
    return result;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    int returnSize;
    int* result = reverseLevelOrder(root, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    free(result);
    return 0;
}

C++ implementation

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

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

void helper(TreeNode* node, int level, vector<vector<int>>& levels) {
    if (!node) return;
    if (level == levels.size()) levels.push_back({});
    levels[level].push_back(node->val);
    helper(node->left, level + 1, levels);
    helper(node->right, level + 1, levels);
}

vector<int> reverseLevelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    helper(root, 0, levels);
    vector<int> result;
    for (int i = levels.size() - 1; i >= 0; --i) {
        result.insert(result.end(), levels[i].begin(), levels[i].end());
    }
    return result;
}

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);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    vector<int> result = reverseLevelOrder(root);
    for (int val : result) cout << val << " ";
    cout << endl;
    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 reverseLevelOrder(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level+1)
        dfs(node.right, level+1)
    dfs(root, 0)
    result = []
    for level in reversed(levels):
        result.extend(level)
    return result

if __name__ == "__main__":
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
    print(reverseLevelOrder(root))

Java implementation

import java.util.*;

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

public class Main {
    public static List<Integer> reverseLevelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        dfs(root, 0, levels);
        List<Integer> result = new ArrayList<>();
        for (int i = levels.size() - 1; i >= 0; i--) {
            result.addAll(levels.get(i));
        }
        return result;
    }

    private static void dfs(TreeNode node, int level, List<List<Integer>> levels) {
        if (node == null) return;
        if (level == levels.size()) levels.add(new ArrayList<>());
        levels.get(level).add(node.val);
        dfs(node.left, level + 1, levels);
        dfs(node.right, level + 1, levels);
    }

    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);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        System.out.println(reverseLevelOrder(root));
    }
}

JavaScript implementation

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

function reverseLevelOrder(root) {
    const levels = [];
    function dfs(node, level) {
        if (!node) return;
        if (level === levels.length) levels.push([]);
        levels[level].push(node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    const result = [];
    for (let i = levels.length - 1; i >= 0; i--) {
        result.push(...levels[i]);
    }
    return result;
}

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

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func reverseLevelOrder(root *TreeNode) []int {
    var levels [][]int
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, level int) {
        if node == nil {
            return
        }
        if level == len(levels) {
            levels = append(levels, []int{})
        }
        levels[level] = append(levels[level], node.Val)
        dfs(node.Left, level+1)
        dfs(node.Right, level+1)
    }
    dfs(root, 0)
    var result []int
    for i := len(levels) - 1; i >= 0; i-- {
        result = append(result, levels[i]...)
    }
    return result
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, &TreeNode{6, nil, nil}, &TreeNode{7, nil, nil}}}
    fmt.Println(reverseLevelOrder(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 reverse_level_order(root: &Option<Box<TreeNode>>) -> Vec<i32> {
    fn dfs(node: &Option<Box<TreeNode>>, level: usize, levels: &mut Vec<Vec<i32>>) {
        if let Some(n) = node {
            if level == levels.len() {
                levels.push(vec![]);
            }
            levels[level].push(n.val);
            dfs(&n.left, level + 1, levels);
            dfs(&n.right, level + 1, levels);
        }
    }

    let mut levels = vec![];
    dfs(root, 0, &mut levels);
    levels.into_iter().rev().flatten().collect()
}

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 {
            val: 3,
            left: Some(Box::new(TreeNode::new(6))),
            right: Some(Box::new(TreeNode::new(7))),
        })),
    }));
    let res = reverse_level_order(&root);
    println!("{:?}", res);
}

Kotlin implementation

class TreeNode(val `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun reverseLevelOrder(root: TreeNode?): List<Int> {
    val levels = mutableListOf<MutableList<Int>>()
    fun dfs(node: TreeNode?, level: Int) {
        if (node == null) return
        if (level == levels.size) levels.add(mutableListOf())
        levels[level].add(node.`val`)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    }
    dfs(root, 0)
    return levels.reversed().flatten()
}

fun main() {
    val root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7))
    )
    println(reverseLevelOrder(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 reverseLevelOrder(root: TreeNode | null): number[] {
    const levels: number[][] = [];
    function dfs(node: TreeNode | null, level: number) {
        if (!node) return;
        if (level === levels.length) levels.push([]);
        levels[level].push(node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    const result: number[] = [];
    for (let i = levels.length - 1; i >= 0; i--) {
        result.push(...levels[i]);
    }
    return result;
}

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