Reverse Level Order Traversal

Problem Statement

Given a binary tree, return the reverse level order traversal of its nodes’ values. (i.e, from left to right and from the last level to starting level).

Examples:
Input:

Output: [15, 7, 9, 20, 3]
Explanation:

• Nodes as level 3 : [15, 7]
• Nodes at level 2: [9, 20]
• Nodes at level 1: [3]
• Reverse level order traversal will be: [15, 7, 9, 20, 3]

Input:

Output: [3, 6, 2, 1]

Approach 1: Recursive DFS

The idea is to apply the recursive approach to solve the problem.

Algorithm

• The recursive function helper takes two parameters, node and levels i.e. the current node and its level.
• Ensure that the tree is not empty.
• In the output list levels, compare the size of levels to node level.
• Append the value of the current node to the node level.
• If the current node contains children nodes, recursively traverse, helper(node -> left / node -> right, level + 1).

C++ Code Implementation

void levelOrder(vector < vector < int >> & ans, TreeNode * node, int level) {
  if (!node) return;
  if (level >= ans.size())
    ans.push_back({});
  ans[level].push_back(node -> val);
  levelOrder(ans, node -> left, level + 1);
  levelOrder(ans, node -> right, level + 1);
}
 
vector < vector < int >> levelOrderBottom(TreeNode * root) {
  vector < vector < int >> ans;
  levelOrder(ans, root, 0);
  reverse(ans.begin(), ans.end());
  return ans;
}

Java Code Implementation

 class Solution {
  List < List < Integer >> levels = new ArrayList < List < Integer >> ();
 
  public void helper(TreeNode node, int level) {
    if (levels.size() == level)
      levels.add(new ArrayList < Integer > ());
 
    levels.get(level).add(node.val);
    if (node.left != null)
      helper(node.left, level + 1);
    if (node.right != null)
      helper(node.right, level + 1);
  }
  public List < List < Integer >> levelOrderBottom(TreeNode root) {
    if (root == null) return levels;
    helper(root, 0);
    Collections.reverse(levels);
    return levels;
  }
}

Python Code Implementation

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if not root:
            return levels
 
        def helper(node, level):
            if len(levels) == level:
                levels.append([])
 
            levels[level].append(node.val)
            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)
 
        helper(root, 0)
        return levels[::-1]

• Time Complexity: O(N), where N is the number of nodes.
• Space Complexity: O(N), for recursion stack.

Approach 2: Iteration: BFS

With a similar idea of recursive traversal, the problem can also be solved using an iterative approach.

Algorithm

• Initialise two queues. The first queue is to determine the current level and the second queue is to determine the next level.
• While the next level queue is not empty, perform the following:
  • Currentlevel =  nextlevel
  • Empty nextlevel queue
  • Traverse through the current level queue and add the value of the node in the final list.
  • Push the left and right child(if it exists) in the queue.
• Reverse the levels.

C++ Code Implementation

vector < vector < int >> levelOrderBottom(TreeNode * root) {
  vector < vector < int >> v;
  if (root == nullptr)
    return {};
 
  queue < TreeNode * > q;
  q.push(root);
 
  while (q.empty() == false) {
    vector < int > res;
    int len = q.size();
    for (int i = 0; i < len; i++) {
      TreeNode * curr = q.front();
      q.pop();
 
      res.push_back(curr -> val);
 
      if (curr -> left)
        q.push(curr -> left);
      if (curr -> right)
        q.push(curr -> right);
    }
    v.push_back(res);
  }
  reverse(v.begin(), v.end());
  return v;
}

Java Code Implementation

 class Solution {
  public List < List < Integer >> levelOrderBottom(TreeNode root) {
    List < List < Integer >> levels = new ArrayList < List < Integer >> ();
    if (root == null) return levels;
 
    ArrayDeque < TreeNode > nextLevel = new ArrayDeque() {
      {
        offer(root);
      }
    };
    ArrayDeque < TreeNode > currLevel = new ArrayDeque();
 
    while (!nextLevel.isEmpty()) {
      currLevel = nextLevel.clone();
      nextLevel.clear();
      levels.add(new ArrayList < Integer > ());
 
      for (TreeNode node: currLevel) {
        levels.get(levels.size() - 1).add(node.val);
        if (node.left != null)
          nextLevel.offer(node.left);
        if (node.right != null)
          nextLevel.offer(node.right);
      }
    }
 
    Collections.reverse(levels);
    return levels;
  }
}

Python Code Implementation

MAX_CHAR = 26
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        levels = []
        next_level = deque([root])
 
        while root and next_level:
            curr_level = next_level
            next_level = deque()
            levels.append([])
 
            for node in curr_level:
                levels[-1].append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
 
        return levels[::-1]

• Time Complexity: O(N),  where N is the number of nodes.
• Space Complexity: O(N), since the queue is used.

Practice Question:

• Reverse Level Order

FAQs

Q.1: How to iteratively solve the problem?

Ans. We use two queues, one for the current level and another for the next level. For each level, iteratively traverse over the tree and keep pushing the node values inside the queues. In the end, reverse the final list.

Q.2: What is the most efficient approach to solving this problem?

Ans. Both recursive and iterative DFS and BFS are the most efficient approaches to solving the problem. The time complexity is O(N) and the space complexity is O(N).