Maximum Number of Leaf Nodes Within a Given Budget

Problem Statement

Given a binary tree and an integer k, we start from the root at level 1.

The cost of visiting a leaf node is equal to the level of that leaf node. We can visit any number of leaf nodes, but the total visiting cost must not exceed k.

Our task is to find the maximum number of leaf nodes that can be visited within the given budget.

Example

Consider the following binary tree:

The leaf nodes are:

Leaf 3 -> Level 3 -> Cost 3
Leaf 3 -> Level 3 -> Cost 3
Leaf 6 -> Level 3 -> Cost 3

Suppose:

k = 8

We can visit two leaves:

3 + 3 = 6

But visiting all three leaves would cost:

3 + 3 + 3 = 9

which exceeds the available budget.

Therefore, the maximum number of leaf nodes we can visit is:

Key Observation

The important observation is that the cost of every leaf is exactly its level.

Therefore, after finding the level of every leaf, the tree itself is no longer important for the selection step. We simply have a collection of costs, where each cost represents one leaf.

For example:

Leaf costs = [3, 3, 3]
Budget = 8

Each visited leaf gives exactly the same benefit: one visited leaf.

Therefore, to maximize the number of leaves, we should always select the leaves with the smallest cost first.

This leads to a greedy strategy:

Find leaf levels
       ↓
Count leaves at each level
       ↓
Process levels from smallest to largest
       ↓
Visit as many leaves as the budget allows

Why the Greedy Approach Works

Suppose we have two available leaves:

Leaf A -> Cost 3
Leaf B -> Cost 5

Both leaves contribute exactly one to the answer.

If a solution chooses the leaf costing 5 while the leaf costing 3 is available, replacing the cost-5 leaf with the cost-3 leaf cannot increase the total cost. The number of visited leaves remains the same, while the amount of remaining budget can only increase.

Therefore, an optimal solution can always choose leaves in nondecreasing order of cost.

Since the cost is the leaf's level, we process the levels from the smallest to the largest.

Why Use a Frequency Array Instead of Sorting?

A straightforward solution would be:

Find all leaf levels
        ↓
Store the levels in an array
        ↓
Sort the array
        ↓
Select the cheapest leaves

Sorting the leaf costs would take O(n log n) time.

However, the problem provides the constraint:

k <= 10^4

A leaf whose level is greater than k can never be visited because its cost alone exceeds the entire budget.

Therefore, we only need to consider costs from 1 through k.

Instead of storing every leaf cost and sorting them, we can maintain a frequency array:

freq[3] = 3
freq[4] = 1

This means:

3 leaves have cost 3
1 leaf has cost 4

Now we can process the costs directly in increasing order.

This changes the selection step from sorting-based processing to a bounded frequency-based approach.

Algorithm

The algorithm consists of two main phases:

Traverse the tree and count leaves by level.
Select the maximum number of leaves using the available budget.

Step 1: Handle an Empty Tree

If root == null, there are no leaf nodes.

Return:

Step 2: Traverse the Tree Using BFS

Use a queue to perform level-order traversal.

The root starts at level 1.

For every level:

Process all nodes belonging to that level.
If a node has no left or right child, it is a leaf.
Increment the frequency of that level.
Add the node's children to the queue.

Because the cost of a leaf is its level, freq[level] represents the number of leaves having that cost.

Step 3: Count Leaf Frequencies

When a leaf is found at level level:

freq[level]++;

For example:

freq[3] = 3

means that three leaves have a visiting cost of 3.

We only need to maintain frequencies up to k, because a leaf with a cost greater than k cannot be visited.

Step 4: Select the Cheapest Leaves

After the BFS traversal, process the frequency array from the smallest cost to the largest.

For each cost:

int canVisit = Math.min(freq[cost], k / cost);

Here:

freq[cost] is the number of leaves available at that cost.
k / cost is the maximum number of leaves with that cost that the remaining budget can afford.

Then update the answer and remaining budget:

count += canVisit;
k -= canVisit * cost;

Once the budget becomes zero, no additional leaf can be visited.

Java Implementation

class Solution {
    public int getCount(Node root, int k) {
        if (root == null) {
            return 0;
        }

        // freq[level] = number of leaf nodes at this level
        int[] freq = new int[k + 1];

        // Queue for level-order traversal
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        int level = 1;

        while (!queue.isEmpty() && level <= k) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Node curr = queue.poll();

                // Check whether the current node is a leaf
                if (curr.left == null && curr.right == null) {
                    freq[level]++;
                }

                // Add left child
                if (curr.left != null) {
                    queue.offer(curr.left);
                }

                // Add right child
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }

            level++;
        }

        // Visit leaves with the lowest cost first
        int count = 0;

        for (int cost = 1; cost <= k; cost++) {
            if (freq[cost] == 0) {
                continue;
            }

            // Maximum number of leaves we can visit at this cost
            int canVisit = Math.min(freq[cost], k / cost);

            count += canVisit;

            // Update the remaining budget
            k -= canVisit * cost;

            if (k == 0) {
                break;
            }
        }

        return count;
    }
}

Code Explanation

BFS Traversal

The queue is used to process the tree level by level:

Queue<Node> queue = new LinkedList<>();
queue.offer(root);

The root is placed in the queue first.

We maintain the current level using:

int level = 1;

At the beginning of each iteration, queue.size() gives the number of nodes belonging to the current level:

int size = queue.size();

for (int i = 0; i < size; i++) {
    Node curr = queue.poll();

Processing exactly size nodes ensures that all nodes processed in this iteration belong to the same level.

Identifying Leaf Nodes

A node is a leaf when it has neither a left child nor a right child:

if (curr.left == null && curr.right == null) {
    freq[level]++;
}

Because the cost of a leaf equals its level, incrementing freq[level] records the number of leaves having that cost.

Adding Children

For every non-null child, add it to the queue:

if (curr.left != null) {
    queue.offer(curr.left);
}

if (curr.right != null) {
    queue.offer(curr.right);
}

These nodes will be processed at the next level.

Selecting the Cheapest Leaves

After the BFS traversal, we process the frequency array:

for (int cost = 1; cost <= k; cost++) {

The loop starts with the smallest possible cost.

Suppose:

freq[3] = 5
k = 8

There are five leaves costing 3, but the budget can afford only:

8 / 3 = 2

leaves.

Therefore:

int canVisit = Math.min(freq[cost], k / cost);

gives:

canVisit = min(5, 2)
         = 2

We then update the result and remaining budget:

count += canVisit;
k -= canVisit * cost;

After visiting two leaves costing 3 each:

count = 2
k = 8 - (2 * 3)
k = 2

No leaf costing 3 or more can now be visited with the remaining budget.

Dry Run

Consider the following tree:

and:

k = 8

Step 1: Traverse the Tree

The levels are:

Level 1: 10
Level 2: 8, 2
Level 3: 3, 3, 6

All three leaf nodes are at level 3.

Therefore:

freq[3] = 3

Step 2: Select Leaves

Initial state:

Budget = 8
Count = 0

At cost 3:

Available leaves = 3
Affordable leaves = 8 / 3 = 2

Therefore:

canVisit = min(3, 2)
         = 2

Update:

Count = 2
Budget = 8 - (2 * 3)
       = 2

The remaining budget is 2, which is not enough to visit another leaf because the cheapest available leaf costs 3.

Therefore:

Answer = 2

Edge Cases

Empty Tree

If the tree is empty:

root = null

there are no leaves to visit.

The answer is:

Root Is a Leaf

If the tree contains only the root:

root[] = [1]

the root is a leaf at level 1.

If:

k >= 1

the leaf can be visited, so the answer is:

The BFS implementation handles this case automatically.

Budget Is Smaller Than the Minimum Leaf Cost

Suppose the cheapest leaf is at level 3, but:

k = 2

No leaf can be visited because even the cheapest leaf costs more than the available budget.

Therefore, the answer is:

Budget Is Exactly Enough

Suppose the leaf costs are:

2, 2, 3

and:

k = 4

We can visit:

2 + 2 = 4

Therefore, the answer is:

Complexity Analysis

Let n be the number of nodes in the binary tree.

Time Complexity

The BFS traversal processes each visited tree node once.

In the worst case, this takes:

O(n)

The frequency array is then processed from cost 1 through k:

O(k)

Therefore, the overall time complexity is:

O(n + k)

Since k <= 10^4, the frequency-array processing is efficient.

Auxiliary Space

The frequency array requires:

O(k)

The BFS queue can contain up to O(n) nodes in the worst case.

Therefore, the total auxiliary space is:

O(n + k)

Key Takeaways

The cost of a leaf node is determined by its level.
Every visited leaf provides the same benefit: one additional leaf in the answer.
Therefore, selecting the cheapest leaves first is optimal.
BFS is used to determine the level of every leaf.
A frequency array avoids sorting all leaf costs.
Because k <= 10^4, storing frequencies for costs from 1 to k is practical.
The overall time complexity is O(n + k).
The overall auxiliary space complexity is O(n + k).

Final Complexity

Time Complexity:  O(n + k)
Auxiliary Space: O(n + k)

Summary

The solution combines Breadth-First Search, a frequency array, and a greedy selection strategy to maximize the number of leaf nodes that can be visited within a given budget. BFS determines the level, and therefore the cost, of every leaf node. Because every visited leaf contributes exactly one to the answer, choosing leaves with the smallest costs first is optimal. Instead of sorting all leaf costs, the solution counts how many leaves occur at each level and processes those levels in increasing order. With k <= 10^4, this frequency-based approach provides an efficient O(n + k) time solution with O(n + k) auxiliary space.