ProgramGuru

Reverse Level Order Traversal of a Binary Tree using Iteration

Problem and examples

Given a binary tree, return the reverse level order traversal of its nodes' values. Reverse level order means visiting the nodes level by level from bottom to top, and within each level from left to right. Use an iterative approach for the traversal.
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 - Iteration

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 our goal is to perform a reverse level order traversal. That means instead of visiting nodes from top to bottom and left to right (like in standard level order), we visit nodes from the bottom level up, and within each level, from left to right.

This problem tests your understanding of tree traversal techniques, especially level order traversal using a queue, and how to reverse the result using a stack. We'll go through this step-by-step using an example to help build your intuition.

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Let's consider the binary tree represented as: [1, 2, 3, 4, 5, null, 6]. Visually, it looks like this:


        1
       /       2   3
     /         4   5    6

Step 2: Use a Queue for Level Order Traversal

We start from the root (node 1) and traverse level by level using a queue. We enqueue the right child before the left child so that when we later reverse the result using a stack, the left-to-right order of nodes is preserved in each level.

Step 3: Push Visited Nodes into a Stack

As we process nodes from the queue, we push each visited node into a stack. This stack helps us reverse the traversal order — since the last nodes processed will come first when popping from the stack.

Step 4: Pop from the Stack for Final Result

Once all nodes have been processed in the queue, we pop elements one by one from the stack to build our final result: the reverse level order traversal.

Step 5: Apply the Steps to the Example

Queue processing order: 1 → 3 → 2 → 6 → 5 → 4 (right before left)

Stack content after traversal: [1, 3, 2, 6, 5, 4]

Final result after popping from stack: [4, 5, 6, 2, 3, 1]

Edge Cases

Case 1: Empty Tree

If the tree is empty (i.e., root is null), then there are no nodes to traverse. We simply return an empty list.

Case 2: Single Node Tree

If the tree has only the root node, the reverse level order traversal is just the value of that single node.

Case 3: Left-Skewed or Right-Skewed Tree

Even in skewed trees (where nodes exist only on one side), the algorithm works correctly — the queue processes each level one by one, and the stack ensures reverse order is achieved.

Finally

This iterative approach to reverse level order traversal is efficient and beginner-friendly. Using a queue to simulate level order traversal and a stack to reverse the result gives us full control over the output structure.

It's important to understand why we enqueue right before left — it ensures the final popped order respects left-to-right orientation per level. Mastering this pattern will help you in many other tree-related problems involving bottom-up traversal.

  1. If the binary tree is empty, return an empty result.
  2. Initialize an empty queue and push the root node onto it.
  3. Initialize an empty stack.
  4. While the queue is not empty, dequeue a node from the front, push it onto the stack, then enqueue its right child (if it exists) followed by its left child (if it exists).
  5. Once the queue is empty, pop all nodes from the stack and record their values. This produces the reverse 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* reverseLevelOrder(TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    TreeNode** queue = malloc(100 * sizeof(TreeNode*));
    TreeNode** stack = malloc(100 * sizeof(TreeNode*));
    int front = 0, rear = 0, top = -1;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* node = queue[front++];
        stack[++top] = node;
        if (node->right) queue[rear++] = node->right;
        if (node->left) queue[rear++] = node->left;
    }
    int* result = malloc(100 * sizeof(int));
    int index = 0;
    while (top >= 0) {
        result[index++] = stack[top--]->val;
    }
    *returnSize = index;
    free(queue);
    free(stack);
    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);
    int returnSize;
    int* res = reverseLevelOrder(root, &returnSize);
    printf("Reverse Level Order Traversal: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return 0;
}

C++ implementation

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

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

vector<int> reverseLevelOrder(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    queue<TreeNode*> q;
    stack<TreeNode*> s;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        s.push(node);
        if (node->right) q.push(node->right);
        if (node->left) q.push(node->left);
    }
    while (!s.empty()) {
        result.push_back(s.top()->val);
        s.pop();
    }
    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);
    vector<int> res = reverseLevelOrder(root);
    cout << "Reverse Level Order Traversal: ";
    for (int val : res) 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):
    if not root:
        return []
    from collections import deque
    queue = deque([root])
    stack = []
    while queue:
        node = queue.popleft()
        stack.append(node)
        if node.right:
            queue.append(node.right)
        if node.left:
            queue.append(node.left)
    return [node.val for node in reversed(stack)]

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

Java implementation

import java.util.*;

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

public class ReverseLevelOrder {
    public List<Integer> reverseLevelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            stack.push(node);
            if (node.right != null) queue.offer(node.right);
            if (node.left != null) queue.offer(node.left);
        }
        while (!stack.isEmpty()) {
            result.add(stack.pop().val);
        }
        return result;
    }
    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);
        ReverseLevelOrder obj = new ReverseLevelOrder();
        System.out.println(obj.reverseLevelOrder(root));
    }
}

JavaScript implementation

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

function reverseLevelOrder(root) {
    if (!root) return [];
    const queue = [root];
    const stack = [];
    while (queue.length) {
        const node = queue.shift();
        stack.push(node);
        if (node.right) queue.push(node.right);
        if (node.left) queue.push(node.left);
    }
    return stack.reverse().map(node => node.val);
}

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

Go implementation

package main

import (
    "fmt"
)

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

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

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    fmt.Println(reverseLevelOrder(root))
}

Rust implementation

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn reverse_level_order(root: Option<Box<TreeNode>>) -> Vec<i32> {
    if root.is_none() {
        return vec![];
    }
    let mut queue = VecDeque::new();
    let mut stack = vec![];
    queue.push_back(root);
    while let Some(Some(node)) = queue.pop_front() {
        stack.push(node.val);
        if node.right.is_some() {
            queue.push_back(node.right);
        }
        if node.left.is_some() {
            queue.push_back(node.left);
        }
    }
    stack.reverse();
    stack
}

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

Kotlin implementation

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

fun reverseLevelOrder(root: TreeNode?): List<Int> {
    if (root == null) return emptyList()
    val queue = ArrayDeque<TreeNode>()
    val stack = ArrayDeque<TreeNode>()
    queue.add(root)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        stack.addFirst(node)
        node.right?.let { queue.add(it) }
        node.left?.let { queue.add(it) }
    }
    return stack.map { it.`val` }
}

fun main() {
    val root = TreeNode(1).apply {
        left = TreeNode(2).apply {
            left = TreeNode(4)
            right = TreeNode(5)
        }
        right = TreeNode(3)
    }
    println(reverseLevelOrder(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 reverseLevelOrder(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var queue: [TreeNode] = [root]
    var stack: [TreeNode] = []
    while !queue.isEmpty {
        let node = queue.removeFirst()
        stack.append(node)
        if let right = node.right {
            queue.append(right)
        }
        if let left = node.left {
            queue.append(left)
        }
    }
    return stack.reversed().map { $0.val }
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
print(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[] {
    if (!root) return [];
    const queue: TreeNode[] = [root];
    const stack: TreeNode[] = [];
    while (queue.length > 0) {
        const node = queue.shift()!;
        stack.push(node);
        if (node.right) queue.push(node.right);
        if (node.left) queue.push(node.left);
    }
    return stack.reverse().map(node => node.val);
}

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