Question

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

For example:Given binary tree [3,9,20,null,null,15,7],

    3
   / \\
  9  20
    /  \\
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Code

vector<vector<int>> levelOrderBottom(TreeNode* root) {
        
    // bfs and push a level into stack.
    
    if(root==NULL) return {};
    
    vector<vector<int>> res;
    
    queue<TreeNode*> q;
    q.push(root);
    stack<vector<int>> s;
    
    
    while(!q.empty()) {
        
        int qSize = q.size();
        vector<int> level;

        // iterate through a level
        for(int i=0; i<qSize; i++) {
        
            TreeNode* node = q.front();
            q.pop();
            
            if(node->left) 
                q.push(node->left);

            if(node->right) 
                q.push(node->right);
            
            level.push_back(node->val);

        }
        s.push(level);
        level.clear();
    }
    
    
    while(!s.empty()){
        res.push_back(s.top());
        s.pop();
    }
    return res;
}

Approach

We traverse the tree in a BFS fashion and save all the nodes of same level in an array. We want the last level to be at the beginning of our resultant array so we use stack. We pop the arrays from stack to push to resultant array.

We could also do this without stack by inserting in the beginning of our resultant array but insertion in the beginning of an array is O(n) operation we we leverage stack instead.

Complexity

Space

O(n) space for queue and for stack so in total ⇒ O(n)

Time

O(n) for iterating the tree and O(levels_in_the_tree) time to push the entries from stack to the resultant array.