- Problem Statement<\/a><\/li>
- Approach 1: Recursive DFS<\/a><\/li>
- C++ Code Implementation<\/a><\/li>
- Java Code Implementation<\/a><\/li>
- Python Code Implementation<\/a><\/li><\/ul>
- Approach 2: Iteration: BFS<\/a><\/li>
- C++ Code Implementation<\/a><\/li>
- Java Code Implementation<\/a><\/li>
- Python Code Implementation<\/a><\/li><\/ul>
- Practice Question:<\/a><\/li>
- FAQs<\/a><\/li>
- Q.1: How to iteratively solve the problem?<\/a><\/li>
- Q.2: What is the most efficient approach to solving this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given a binary tree, return the reverse level order traversal of its nodes\u2019 values. (i.e, from left to right and from the last level to starting level).<\/p>\n\n\n\n
Examples:<\/strong>
Input:<\/strong><\/p>\n\n\n\n<\/figure><\/div>\n\n\n\n
Output:<\/strong> [15, 7, 9, 20, 3]
Explanation:<\/strong><\/p>\n\n\n\n- Nodes as level 3 : [15, 7]<\/li>
- Nodes at level 2: [9, 20]<\/li>
- Nodes at level 1: [3]<\/li>
- Reverse level order traversal will be: [15, 7, 9, 20, 3]<\/li><\/ul>\n\n\n\n
Input:<\/strong><\/p>\n\n\n\n
Output:<\/strong> [3, 6, 2, 1]\n\n\n\n
Approach 1: Recursive DFS<\/h2>\n\n\n\n
The idea is to apply the recursive approach to solve the problem.<\/p>\n\n\n\n
Algorithm<\/strong><\/p>\n\n\n\n
- The recursive function helper <\/strong>takes two parameters, node <\/strong>and levels <\/strong>i.e. the current node and its level.<\/li>
- Ensure that the tree is not empty.<\/li>
- In the output list levels<\/strong>, compare the size of levels<\/strong> to node <\/strong>level.<\/li>
- Append the value of the current node to the node level<\/strong>.<\/li>
- If the current node contains children nodes, recursively traverse, helper(node -> left \/ node -> right, level + 1)<\/strong>.<\/li><\/ul>\n\n\n\n
C++ Code Implementation<\/span><\/h3>\n\n\n\n
void levelOrder(vector < vector < int >> & ans, TreeNode * node, int level) {\n if (!node) return;\n if (level >= ans.size())\n ans.push_back({});\n ans[level].push_back(node -> val);\n levelOrder(ans, node -> left, level + 1);\n levelOrder(ans, node -> right, level + 1);\n}\n \nvector < vector < int >> levelOrderBottom(TreeNode * root) {\n vector < vector < int >> ans;\n levelOrder(ans, root, 0);\n reverse(ans.begin(), ans.end());\n return ans;\n}<\/pre>\n\n\n\nJava Code Implementation<\/span><\/h3>\n\n\n\n
class Solution {\n List < List < Integer >> levels = new ArrayList < List < Integer >> ();\n \n public void helper(TreeNode node, int level) {\n if (levels.size() == level)\n levels.add(new ArrayList < Integer > ());\n \n levels.get(level).add(node.val);\n if (node.left != null)\n helper(node.left, level + 1);\n if (node.right != null)\n helper(node.right, level + 1);\n }\n public List < List < Integer >> levelOrderBottom(TreeNode root) {\n if (root == null) return levels;\n helper(root, 0);\n Collections.reverse(levels);\n return levels;\n }\n}<\/pre>\n\n\n\nPython Code Implementation<\/span><\/h3>\n\n\n\n
class Solution:\n def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n levels = []\n if not root:\n return levels\n \n def helper(node, level):\n if len(levels) == level:\n levels.append([])\n \n levels[level].append(node.val)\n if node.left:\n helper(node.left, level + 1)\n if node.right:\n helper(node.right, level + 1)\n \n helper(root, 0)\n return levels[::-1]<\/pre>\n\n\n\n
- Time Complexity:<\/strong> O(N), where N is the number of nodes.<\/li>
- Space Complexity:<\/strong> O(N), for recursion stack.<\/li><\/ul>\n\n\n\n
Approach 2: Iteration: BFS<\/h2>\n\n\n\n
With a similar idea of recursive traversal, the problem can also be solved using an iterative approach.<\/p>\n\n\n\n
Algorithm<\/strong><\/p>\n\n\n\n
- Initialise two queues. The first queue is to determine the current level and the second queue is to determine the next level.<\/li>
- While the next level queue is not empty, perform the following:
- Currentlevel = nextlevel<\/li>
- Empty nextlevel queue<\/li>
- Traverse through the current level queue and add the value of the node in the final list.<\/li>
- Push the left and right child(if it exists) in the queue.<\/li><\/ul><\/li>
- Reverse the levels.<\/li><\/ul>\n\n\n\n
C++ Code Implementation<\/h3>\n\n\n\n
vector < vector < int >> levelOrderBottom(TreeNode * root) {\n vector < vector < int >> v;\n if (root == nullptr)\n return {};\n \n queue < TreeNode * > q;\n q.push(root);\n \n while (q.empty() == false) {\n vector < int > res;\n int len = q.size();\n for (int i = 0; i < len; i++) {\n TreeNode * curr = q.front();\n q.pop();\n \n res.push_back(curr -> val);\n \n if (curr -> left)\n q.push(curr -> left);\n if (curr -> right)\n q.push(curr -> right);\n }\n v.push_back(res);\n }\n reverse(v.begin(), v.end());\n return v;\n}<\/pre>\n\n\n\nJava Code Implementation<\/h3>\n\n\n\n
class Solution {\n public List < List < Integer >> levelOrderBottom(TreeNode root) {\n List < List < Integer >> levels = new ArrayList < List < Integer >> ();\n if (root == null) return levels;\n \n ArrayDeque < TreeNode > nextLevel = new ArrayDeque() {\n {\n offer(root);\n }\n };\n ArrayDeque < TreeNode > currLevel = new ArrayDeque();\n \n while (!nextLevel.isEmpty()) {\n currLevel = nextLevel.clone();\n nextLevel.clear();\n levels.add(new ArrayList < Integer > ());\n \n for (TreeNode node: currLevel) {\n levels.get(levels.size() - 1).add(node.val);\n if (node.left != null)\n nextLevel.offer(node.left);\n if (node.right != null)\n nextLevel.offer(node.right);\n }\n }\n \n Collections.reverse(levels);\n return levels;\n }\n}<\/pre>\n\n\n\nPython Code Implementation<\/h3>\n\n\n\n
MAX_CHAR = 26\nclass Solution:\n def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n levels = []\n next_level = deque([root])\n \n while root and next_level:\n curr_level = next_level\n next_level = deque()\n levels.append([])\n \n for node in curr_level:\n levels[-1].append(node.val)\n if node.left:\n next_level.append(node.left)\n if node.right:\n next_level.append(node.right)\n \n return levels[::-1]<\/pre>\n\n\n\n
- Space Complexity:<\/strong> O(N), for recursion stack.<\/li><\/ul>\n\n\n\n
- The recursive function helper <\/strong>takes two parameters, node <\/strong>and levels <\/strong>i.e. the current node and its level.<\/li>
- Q.2: What is the most efficient approach to solving this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code Implementation<\/a><\/li>
- Java Code Implementation<\/a><\/li>
- Approach 1: Recursive DFS<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input-1024x727.png\")
<\/figure><\/div>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Input2-1024x727.png\")
<\/figure><\/div>\n\n\n\n