DEV Community

Ayan Banerjee
Ayan Banerjee

Posted on • Originally published at csposts.com on

Interview Problem: Binary Tree Reverse Level Order Traversal

#cpp #interview #bfs #dfs

Given a binary tree, print its reverse level order traversal. For example, given this tree -

 3 / \ 2 8 / \ 1 9
Enter fullscreen mode Exit fullscreen mode

print -

[ [1, 9], [2, 8], [3] ]
Enter fullscreen mode Exit fullscreen mode

Approach - 1: BFS

We can simply perform a BFS traversal and reverse the resulting traversal.

animated-bfs

By Blake Matheny - Transferred from en.wikipedia to Commons., CC BY-SA 3.0, Link

vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> bfsTraversal; // perform bfs queue<TreeNode*> q; if (root) q.push(root); while(!q.empty()) { int levelSize = q.size(); vector<int> curLevelTraversal(levelSize); for (int i = 0; i < levelSize; ++i) { TreeNode* current = q.front(); q.pop(); curLevelTraversal[i] = current -> val; if (current -> left) q.push(current -> left); if (current -> right) q.push(current -> right); } bfsTraversal.push_back(curLevelTraversal); } reverse(bfsTraversal.begin(), bfsTraversal.end()); return bfsTraversal; }
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(N) due to BFS

Space Complexity: O(N) as we are storing nodes in the queue

Approach - 2: DFS

This problem can also be solved using DFS. It’s important that we should visit the left child first and then the right child. As we go from a parent node to its child nodes, we increase the level. We also store them in a vector and return its reverse.

void dfs(TreeNode *node, vector<vector<int>> &reverseLevelTraversal, int level) { if (node == nullptr) return; if (level >= reverseLevelTraversal.size()) { reverseLevelTraversal.push_back({}); } reverseLevelTraversal[level].push_back(node -> val); // increase level if when we go to children nodes dfs(node -> left, reverseLevelTraversal, level + 1); dfs(node -> right, reverseLevelTraversal, level + 1); } vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> reverseLevelTraversal; // start with level 0 dfs(root, reverseLevelTraversal, 0); reverse(reverseLevelTraversal.begin(), reverseLevelTraversal.end()); return reverseLevelTraversal; }
Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(N) due to DFS

Space Complexity: O(N) for recursion stack space

Exercise: Use stack to perform DFS.

Top comments (0)