# LeetCode: 107. Binary Tree Level Order Traversal II

**The Problem**

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).

**Example**

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

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 2000]`

. `-1000 <= Node.val <= 1000`

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

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

ðŸ§

Github with all the solution including test cases.

Let's break down the code step by step:

`vector<vector<int>> levelOrderBottom(TreeNode* root)`

: This is the main function that initiates the process. It takes the root of the binary tree as an argument.`vector<vector<int>> ans;`

:`ans`

is a 2D vector that will store the result of the bottom-up level order traversal.`levelOrderBottomHelper(root, ans, 0);`

: This line calls the helper function`levelOrderBottomHelper`

to perform the traversal. It starts at the root of the tree with level 0.`reverse(ans.begin(), ans.end());`

: After the traversal is complete, this line reverses the`ans`

vector. This reversal is necessary because the traversal builds the result from top to bottom, so reversing it at the end gives the desired bottom-up order.`return ans;`

: The reversed`ans`

vector is returned as the final result.

Now, let's look at the `levelOrderBottomHelper`

function:

`void levelOrderBottomHelper(TreeNode* root, vector<vector<int>> &levels, int level)`

: This is the recursive helper function that performs the traversal.`if (root == nullptr) return;`

: If the`root`

node is null (indicating an empty subtree), the function returns immediately.`int nextLevel = level + 1;`

:`nextLevel`

is incremented to keep track of the next level in the traversal.`if (levels.size() < nextLevel) levels.resize(nextLevel);`

: This code ensures that there is enough space in the`levels`

vector to store values for the current level. If not, it resizes the`levels`

vector to accommodate the new level.`levelOrderBottomHelper(root->left, levels, nextLevel);`

: Recursive call to traverse the left subtree, passing the updated level.`levelOrderBottomHelper(root->right, levels, nextLevel);`

: Recursive call to traverse the right subtree, passing the updated level.`levels[level].push_back(root->val);`

: This line adds the value of the current node (`root->val`

) to the appropriate level in the`levels`

vector. The`level`

variable determines which level to add the value to.