algoadvance

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

Clarifying Questions

  1. Q: What should be returned if the tree is empty? A: Return an empty list.
  2. Q: Are the node values unique? A: Yes, for simplicity, assume all node values are unique.

Strategy

To solve the problem, we will perform a level-order traversal of the binary tree, but instead of constructing the result in a top-down manner, we’ll build it from the bottom up.

Steps:

  1. Check if the tree is empty: If the root is nullptr, return an empty list.
  2. Use a queue for the level-order traversal: Initialize a queue to store nodes at the current level.
  3. Traverse each level:
    • Determine the number of nodes at the current level.
    • For each node, add its value to the current level’s list and enqueue its non-null children.
    • Prepend the current level’s list to the result list.
  4. Return the result: Once all levels are processed, the result list will be bottom-up.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // for reverse

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* currentNode = q.front();
                q.pop();
                currentLevel.push_back(currentNode->val);
                
                if (currentNode->left != nullptr)  q.push(currentNode->left);
                if (currentNode->right != nullptr) q.push(currentNode->right);
            }
            result.push_back(currentLevel);
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

// Helper function to print the result
void printResult(const vector<vector<int>>& result) {
    for (const auto& level : result) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << endl;
    }
}

int main() {
    // Create a sample binary tree: 3
    //                            /   \
    //                           9     20
    //                                /  \
    //                               15   7
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    Solution sol;
    vector<vector<int>> result = sol.levelOrderBottom(root);
    printResult(result);
    
    // Clean up the tree (not necessary in production code)
    delete root->right->right;
    delete root->right->left;
    delete root->right;
    delete root->left;
    delete root;
    
    return 0;
}

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the tree:

Space Complexity

The space complexity is O(n) as well:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI