Reverse Level Order Traversal of a Binary Tree using Recursion

Problem Statement❯

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.

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: Normal Tree with Multiple Levels

In this case, we have a binary tree with multiple levels. To solve this, we recursively gather nodes level by level starting from the root and store each level in a separate list. Once we finish all levels, we reverse the list of levels. This way, the bottom-most level comes first, followed by the level above it, and so on, until we reach the root level. Finally, we flatten this list to get a single array representing the reverse level order traversal.

Case 2: Tree with Single Node

If the binary tree has only one node (i.e., just the root), then there is only one level. In reverse level order, this is still the only node present. The output will be a list containing just that root value.

Case 3: Empty Tree

In this case, the binary tree is null or empty. Since there are no nodes to traverse, the output should be an empty list. It’s important to handle this case explicitly in code to avoid errors such as null reference exceptions.

Summary

Reverse level order traversal is the process of visiting nodes from bottom to top and left to right within each level. Using recursion, we collect values for each level, then reverse the collection of levels, and finally flatten the result. This approach ensures that we maintain both vertical (levels) and horizontal (left-to-right) orderings as per the traversal’s definition.

Algorithm Steps❯

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

Code

Python

Java

JavaScript

C++

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 helper(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        helper(node.left, level + 1)
        helper(node.right, level + 1)
    helper(root, 0)
    result = []
    for level in reversed(levels):
        result.extend(level)
    return result

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

⬅ Previous TopicReverse Level Order Traversal of a Binary Tree using Iteration

Next Topic ⮕Find Height of a Binary Tree

Comments

Loading comments...