Visit Leaves with Budget

Problem Overview

Visiting a leaf costs its level, with the root at level 1.

Intuition

Visiting a leaf costs its level, with the root at level 1. To maximize how many leaves you can afford, always buy the cheapest ones first. Level order traversal already meets leaves in nondecreasing cost order, so a BFS can take them greedily without sorting.

Algorithm

1If the tree is empty, return 0.
2BFS from the root, tracking the current level.
3When a leaf appears, if its level exceeds the remaining budget, stop and return the count so far.
4Otherwise subtract the level from the budget and increment the count.
5Enqueue children of non-leaf nodes and advance the level after each wave.
6Return the count when the queue is empty or the budget is spent.

Example Walkthrough

Input: budget 8, leaves at levels 3, 3, and 4

1. BFS reaches the two level-3 leaves first and spends 6.
2. The next leaf costs 4, which is more than the remaining 2, so stop.
3. Two leaves were taken.

Output: 2

Common Pitfalls

• Root level must be 1, not 0.
• Internal nodes have no visit cost; only leaves do.
• Stop as soon as the next leaf is too expensive; deeper leaves only cost more.
• Same-level leaves share one cost, so order among them does not matter.

Visit Leaves with Budget.java

Java

// Approach: Cost of a leaf is its level (root = 1). Maximize count by taking
// cheapest leaves first. BFS visits levels in order, so leaf costs appear
// already sorted; take greedily and stop when the next leaf exceeds budget.
// Complexity: O(n) time, O(w) space (w = max width).
import java.util.*;

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

        Queue<Node> q = new ArrayDeque<>();
        q.offer(root);
        int level = 1, count = 0;

        while (!q.isEmpty() && k > 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                if (node.left == null && node.right == null) {
                    if (level > k)
                        return count;
                    k -= level;
                    count++;
                } else {
                    if (node.left != null)
                        q.offer(node.left);
                    if (node.right != null)
                        q.offer(node.right);
                }
            }
            level++;
        }

        return count;
    }
}

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
    }
}

Was this solution helpful?