Reverse Level Order Traversal of a Binary Tree using Iteration

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

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.

Examples❯

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

Visualization Player

Solution❯

Case 1: Empty Tree

If the tree is empty (i.e., no root node), there are no nodes to process. In this case, we return an empty list immediately.

Case 2: Tree with a Single Node

When the tree consists of only one node, that node is the only element in the reverse level order traversal. So the output is simply a list containing the value of that single node.

Case 3: Tree with Multiple Levels

For trees with multiple levels, we traverse the tree level by level starting from the root. However, instead of storing nodes in a result list directly, we first push them into a stack while traversing in a modified order: we enqueue the right child before the left child. This way, when we later pop from the stack, the left-to-right order within each level is preserved, and the levels themselves are reversed (bottom-up).

Using a queue ensures we process nodes in level order, and a stack helps us reverse the final output. For example, in the tree with nodes [1, 2, 3, 4, 5, null, 6], our traversal would push nodes in the order [1, 3, 2, 6, 5, 4] into the stack. Popping from the stack gives us the desired reverse level order: [4, 5, 6, 2, 3, 1].

Algorithm Steps❯

  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.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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)
    result = []
    while stack:
        result.append(stack.pop().val)
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(reverseLevelOrder(root))