## DEV Community

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Binary Tree Level Order Traversal II

### Problem statement

Given the `root` of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Problem statement taken from: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Example 1:

``````Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[15, 7], [9, 20], ]
``````

Example 2:

``````Input: root = 
Output: []
``````

Example 3:

``````Input: root = []
Output: []
``````

Constraints:

``````- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
``````

### Explanation

The problem statement is similar to our old blog post LeetCode Binary Tree Level Order Traversal. Instead of printing the levels row by row from top to bottom, we need to print them in reverse order.

#### Recursive function

We can modify the Recursive Solution of LeetCode Binary Tree Level Order Traversal to print the tree level from bottom to top.

A C++ snippet of the solution will be as below.

``````void reverseLevelOrder(node* root) {
int h = height(root);
int i;

for(i = h; i >= 1; i--)
printGivenLevel(root, i);
}

void printGivenLevel(node* root, int level) {
if (root == NULL)
return;

if (level == 1)
cout << root->data << ' ';
else if (level > 1)
{
printGivenLevel(root->left, level - 1);
printGivenLevel(root->right, level - 1);
}
}

int height(node* node) {
if (node == NULL)
return 0;
else
{
int lheight = height(node->left);
int rheight = height(node->right);

if (lheight > rheight)
return(lheight + 1);
else return(rheight + 1);
}
}
``````

The time-complexity of the above approach is O(n^2), and the space complexity is O(n).

#### Queues: Iterative Solution

We can reduce the time complexity to O(n), using an iterative approach with Queues.

Let's check the algorithm.

``````- initialize 2D array as vector vector<vector<int>> result
- initialize size and i

- return result if root == null

- initialize queue<TreeNode*> q
- push root to queue : q.push(root)

- initialize TreeNode* node for iterating on the tree

- loop while( !q.empty() ) // queue is not empty
- initialize vector<int> tmp
- set size = q.size()

- loop for i = 0; i < size; i++
- set node = q.front()

- if node->left
- push in queue: q.push(node->left)

- if node->right
- push in queue: q.push(node->right)

- remove the front node: q.pop()
- push node->val to tmp. tmp.push_back(node->val)

- push the tmp to result: result.push_back(tmp)
- loop while end

- reverse result

- return result
``````

The time complexity of the above approach is O(n), and the space complexity is O(n).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
int size, i;

if(root == NULL)
return result;

queue<TreeNode*> q;
q.push(root);

TreeNode* node;

while(!q.empty()){
vector<int> tmp;
size = q.size();

for(i = 0; i < size; i++){
node = q.front();
if(node->left)
q.push(node->left);

if(node->right)
q.push(node->right);

q.pop();
tmp.push_back(node->val);
}

result.push_back(tmp);
}

reverse(result.begin(), result.end());

return result;
}
};
``````

#### Golang solution

``````func levelOrderBottom(root *TreeNode) [][]int {
result := [][]int{}

queue := []*TreeNode{root}

for len(queue) != 0 {
tmp := []int{}
size := len(queue)

for i := 0; i < size; i++ {
if queue != nil {
tmp = append(tmp, queue.Val)
queue = append(queue, queue.Left)
queue = append(queue, queue.Right)
}

queue = queue[1:]
}

result = append(result, tmp)
}

result = reverse(result)

return result[1:]
}

func reverse(input [][]int) [][]int {
var output [][]int

for i := len(input) - 1; i >= 0; i-- {
output = append(output, input[i])
}

return output
}
``````

#### Javascript solution

``````var levelOrderBottom = function(root) {
let result = [];
let queue = [];

if(root)
queue.push(root);

while(queue.length > 0) {
tmp = [];
let len = queue.length;

for (let i = 0; i< len; i++) {
let node = queue.shift();
tmp.push(node.val);

if(node.left) {
queue.push(node.left);
}

if(node.right) {
queue.push(node.right);
}
}

result.push(tmp);
}

return result.reverse();
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: root = [3, 9, 20, null, null, 15, 7]

Step 1: vector<vector<int>> result;
int size, i;

Step 2: root == null
[3, 9..] == null
false

Step 3: queue<TreeNode*> q;
q.push(root);

q = 

Step 4: loop !q.empty()
q = 
q.empty() = false
!false = true

vector<int> tmp
size = q.size()
= 1

for(i = 0; i < 1; i++)
- 0 < 1
- true

node = q.front()
node = 3

if node->left
- node->left = 9
- q.push(node->left)
- q = [3, 9]

if node->right
- node->right = 20
- q.push(node->right)
- q = [3, 9, 20]

q.pop()
q = [9, 20]

tmp.push_back(node->val)
tmp.push_back(3)

i++
i = 1

for(i < 1)
1 < 1
false

result.push_back(tmp)
result = []

Step 5: loop !q.empty()
q = [9, 20]
q.empty() = false
!false = true

vector<int> tmp
size = q.size()
= 2

for(i = 0; i < 2; i++)
- 0 < 2
- true

node = q.front()
node = 9

if node->left
- node->left = nil
- false

if node->right
- node->right = nil
- false

q.pop()
q = 

tmp.push_back(node->val)
tmp.push_back(9)

i++
i = 1

for(i < 2)
- 1 < 2
- true

node = q.front()
node = 20

if node->left
- node->left = 15
- q.push(node->left)
- q = [20, 15]

if node->right
- node->left = 7
- q.push(node->right)
- q = [20, 15, 7]

q.pop()
q = [15, 7]

tmp.push_back(node->val)
tmp.push_back(20)
tmp = [9, 20]

i++
i = 2

for(i < 2)
- 2 < 2
- false

result.push_back(tmp)
result = [, [9, 20]]

Step 6: loop !q.empty()
q = [15, 7]
q.empty() = false
!false = true

vector<int> tmp
size = q.size()
= 2

for(i = 0; i < 2; i++)
- 0 < 2
- true

node = q.front()
node = 15

if node->left
- node->left = nil
- false

if node->right
- node->right = nil
- false

q.pop()
q = 

tmp.push_back(node->val)
tmp.push_back(15)

i++
i = 1

for(i < 2)
- 1 < 2
- true

node = q.front()
node = 7

if node->left
- node->left = nil
- false

if node->right
- node->right = nil
- false

q.pop()
q = []

tmp.push_back(node->val)
tmp.push_back(7)
tmp = [15, 7]

i++
i = 2

for(i < 2)
- 2 < 2
- false

result.push_back(tmp)
result = [, [9, 20], [15, 7]]

Step 7: loop !q.empty()
q = []
q.empty() = true
!true = false

Step 8: reverse(result.begin(), result.end())

Step 9: return result

So we return the result as [[15, 7], [9, 20], ].
``````