Find Leaves of Binary Tree

Problem Statement

The problem is focused on processing a binary tree by sequentially removing leaf nodes through consecutive operations. Starting with a given binary tree, the objective is to:

1. Identify and collect all leaf nodes of the binary tree.
2. Remove these leaf nodes from the tree.
3. Repeat the above two steps until the entire tree has been dismantled.

The challenge involves not just the removal of nodes, but also the collection of these nodes in the order of their removal. As trees are hierarchical structures, the repeated removal of leaf nodes simulates a peeling process where the outermost leaves are removed first, progressively reaching inwards towards the root. The result should be a list containing sub-lists of nodes, with each sub-list representing a "layer" of leaves removed during one iteration of the process.

Examples

Example 1

Input:

root = [1,2,3,4,5]

Output:

[[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2

Input:

root = [1]

Output:

[[1]]

Constraints

• The number of nodes in the tree is in the range [1, 100].
• -100 <= Node.val <= 100

Approach and Intuition

When solving the problem of collecting and removing consecutive layers of leaves from a binary tree until it is empty, we can use a level-by-level traversal approach, but inverted to target the leaf nodes specifically. Here’s the intuitive approach:

1. Base Trees: Understanding how even a small tree behaves can give insights into the solution. Single node trees directly lead to an answer as the root itself is a leaf. Trees with immediate children show peeling off the outer leaves first (children) before getting to the root.

2. Identifying Leaves: A recursive traversal typically used for tree problems, such as Depth-First Search (DFS), can be employed. During this traversal, we can identify nodes that have no children (leaf nodes) and collect them.

3. Storage and Removal: As leaves are identified, they need to be stored in a list as per the level of their removal. These nodes also need to be removed after they are collected, which implies restructuring the parent nodes to not reference the removed leaf nodes anymore.

4. Repeated Action: Once leaves of a level are collected and removed, the process repeats. This implies a loop or recursive call that ends when there are no more nodes to process (i.e., when the tree is empty).

5. Edge Considerations:

   • Single Node: If the tree has only one node, the process stops after one collection.
   • Complex Trees: The approach scales to deeper trees, given the constraints, but ensuring each level is correctly identified and processed in sequence is crucial.

By recursively stripping away the leaves, we effectively perform a breadth-first search (BFS) in a reversed manner. Each recursion or iteration peels away the outermost level, mimicking a level order traversal but from the leaves inwards.

Solutions

class Solution {
private:
    vector<vector<int>> treeLevels;

public:
    int calculateHeight(TreeNode *node) {
        if (!node) {
            return -1;
        }

        int left = calculateHeight(node->left);
        int right = calculateHeight(node->right);
        
        int currentHeight = max(left, right) + 1;
        
        if (treeLevels.size() == currentHeight) {
            treeLevels.push_back({});
        }

        treeLevels[currentHeight].push_back(node->val);
        
        return currentHeight;
    }
    
    vector<vector<int>> gatherLeaves(TreeNode* root) {
        treeLevels.clear();
        
        calculateHeight(root);
        
        return treeLevels;
    }
};

class Solution {

    private List<List<Integer>> leafLevels;

    private int calculateHeight(TreeNode node) {
        if (node == null) {
            return -1;
        }

        int left = calculateHeight(node.left);
        int right = calculateHeight(node.right);

        int height = Math.max(left, right) + 1;

        if (leafLevels.size() == height) {
            leafLevels.add(new ArrayList<>());
        }

        leafLevels.get(height).add(node.val);

        return height;
    }

    public List<List<Integer>> findLeaves(TreeNode node) {
        leafLevels = new ArrayList<>();

        calculateHeight(node);

        return leafLevels;
    }
}