Binary TreesProblem 2 of 35

Reverse Level Order traversal

Brute Force
Time: O(n^2)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a binary tree, perform reverse level order traversal - print nodes level by level from bottom to top, left to right within each level.

Example:

1 / \ 2 3 / \ \ 4 5 6
  • Input: Root of the above tree
  • Output: [[4, 5, 6], [2, 3], [1]] or [4, 5, 6, 2, 3, 1]

Approach 1: Brute Force (Using Height)

Intuition

Calculate the height and traverse from the last level to the first level, printing nodes at each level.

Algorithm

  1. Calculate the height of the tree
  2. For each level from height down to 1:
    • Traverse the tree recursively
    • Collect nodes at that level
java
import java.util.*;

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

public class Solution {
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
    
    public void printLevel(TreeNode root, int level, List<Integer> result) {
        if (root == null) return;
        if (level == 1) {
            result.add(root.val);
        } else {
            printLevel(root.left, level - 1, result);
            printLevel(root.right, level - 1, result);
        }
    }
    
    public List<Integer> reverseLevelOrderBruteForce(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        int height = getHeight(root);
        
        // Traverse from bottom to top
        for (int i = height; i >= 1; i--) {
            printLevel(root, i, result);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n^2) - For each level, we traverse the entire tree
  • Space Complexity: O(n) - Recursion stack in worst case

Approach 2: Optimal (Using Queue and Stack)

Intuition

Perform normal level order traversal using a queue, but push each level's result onto a stack. Finally, pop from the stack to get reverse order.

Algorithm

  1. Perform BFS using a queue
  2. Push each node onto a stack while traversing
  3. Pop all elements from stack to get reverse order
java
import java.util.*;

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

public class Solution {
    public List<List<Integer>> reverseLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<List<Integer>> stack = new Stack<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            stack.push(currentLevel);
        }
        
        // Pop from stack to get reverse order
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(n) - Queue and stack together hold all nodes

Key Takeaways

  1. Stack reverses order - Use stack with BFS to reverse the level order
  2. Alternatively, you can do normal level order and reverse the result array
  3. The brute force approach iterates levels in reverse but is less efficient
  4. This is a variation of standard level order traversal
Previous
Level order traversal
Next
Height of a tree