Find Leaves of Binary Tree

Problem

Collect and remove all leaf nodes. Repeat until tree is empty. Return all collected leaves in order.

Key insight: Group nodes by their height (0 = leaf, 1 = parent of leaf, etc.). Post-order: height = 1 + max(left_h, right_h).

Solutions

// C++
vector<vector<int>> result;
int dfs(TreeNode* node) {
    if (!node) return -1;
    int h = 1 + max(dfs(node->left), dfs(node->right));
    if (result.size() == h) result.push_back({});
    result[h].push_back(node->val);
    return h;
}
vector<vector<int>> findLeaves(TreeNode* root) {
    dfs(root); return result;
}

// Java
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> findLeaves(TreeNode root) {
    dfs(root); return result;
}
int dfs(TreeNode node) {
    if (node == null) return -1;
    int h = 1 + Math.max(dfs(node.left), dfs(node.right));
    if (result.size() == h) result.add(new ArrayList<>());
    result.get(h).add(node.val);
    return h;
}

// JavaScript
function findLeaves(root) {
    const result = [];
    function dfs(node) {
        if (!node) return -1;
        const h = 1 + Math.max(dfs(node.left), dfs(node.right));
        if (result.length === h) result.push([]);
        result[h].push(node.val);
        return h;
    }
    dfs(root);
    return result;
}

# Python
def findLeaves(root):
    result = []
    def dfs(node):
        if not node:
            return -1
        h = 1 + max(dfs(node.left), dfs(node.right))
        if len(result) == h:
            result.append([])
        result[h].append(node.val)
        return h
    dfs(root)
    return result

Complexity

Time: O(n)
Space: O(n)