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

```
3
/ \
2 8
/ \
1 9
```

print -

```
[
[1, 9],
[2, 8],
[3]
]
```

## Approach - 1: BFS

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

*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;
}
```

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;
}
```

Time Complexity: `O(N)`

due to DFS

Space Complexity: `O(N)`

for recursion stack space

**Exercise**: Use stack to perform DFS.

## Discussion (0)