02. Leaf under budget

The problem can be found at the following link:

My Approach

I am using a breadth-first search (BFS) approach to traverse the tree.

I maintain a queue to keep track of nodes and their corresponding levels.
As I traverse the tree level by level, I check if a node is a leaf node (both left and right children are null).
- If it is a leaf node and the level is greater than the budget (k), I return the count of leaf nodes found so far.
- Otherwise, I increment the count and subtract the current level from the budget.
If the node has children, I push them into the queue with their corresponding levels.

In this solution, as we traverse from level 1 down to there leaf nodes, it naturally addresses our greedy approach to maximize the number of leaf nodes within our budget, providing the desired answers automatically.

Time and Auxiliary Space Complexity

Time Complexity: The algorithm visits each node in the tree once, so the time complexity is O(N), where N is the number of nodes in the tree.
Auxiliary Space Complexity: The space complexity is O(W), where W is the maximum number of nodes at any level in the tree.

Code (C++)

class Solution {
public:
    int getCount(Node *root, int k) {
        queue<pair<Node*, int>> q;
        q.push({root, 1});
        int cnt = 0;

        while (!q.empty() && k > 0) {
            auto node = q.front().first;
            int level = q.front().second;
            q.pop();

            if (!node->left && !node->right) {
                if (level > k)
                    return cnt;

                ++cnt;
                k -= level;
            } else {
                if (node->left)
                    q.push({node->left, level + 1});
                if (node->right)
                    q.push({node->right, level + 1});
            }
        }

        return cnt;
    }
};

Contribution and Support

Previous09-2023(sep)Next09-2023(sep)

Last updated 1 year ago

Was this helpful?

My Approach

I am using a breadth-first search (BFS) approach to traverse the tree.

I maintain a queue to keep track of nodes and their corresponding levels.

As I traverse the tree level by level, I check if a node is a leaf node (both left and right children are null).

If it is a leaf node and the level is greater than the budget (k), I return the count of leaf nodes found so far.
Otherwise, I increment the count and subtract the current level from the budget.

If the node has children, I push them into the queue with their corresponding levels.

Code (C++)

class Solution {
public:
    int getCount(Node *root, int k) {
        queue<pair<Node*, int>> q;
        q.push({root, 1});
        int cnt = 0;

        while (!q.empty() && k > 0) {
            auto node = q.front().first;
            int level = q.front().second;
            q.pop();

            if (!node->left && !node->right) {
                if (level > k)
                    return cnt;

                ++cnt;
                k -= level;
            } else {
                if (node->left)
                    q.push({node->left, level + 1});
                if (node->right)
                    q.push({node->right, level + 1});
            }
        }

        return cnt;
    }
};