• Expected Output: [[4],[3],[2],[1]]
• Justification: This tree has a linear structure. Each node becomes a leaf one after the other, starting from node 4 to node 1.

Solution

To solve this problem, we employ a depth-first search (DFS) strategy to identify the leaves of the binary tree at each level. The key idea is to traverse the tree from the bottom up. This approach allows us to determine the "height" of each node, with the height of a leaf being 0. The height of a node is the number of edges on the longest downward path between that node and a leaf. By calculating these heights during our DFS traversal, we can group nodes with the same height together, as they will be removed in the same round.

This method is effective because it leverages the natural structure of a binary tree to minimize the amount of work needed to identify leaves at each round. By using the height of nodes as a guide, we avoid the need to repeatedly traverse the entire tree to find leaves. Additionally, this approach ensures that our solution is scalable and can handle trees of various sizes and shapes efficiently.

Step-by-Step Algorithm

1. Implement the DFS Function:

   • Define a recursive function dfs that takes a TreeNode and returns its height. The height of a null node is considered -1. This function performs several key operations:
     • It first checks if the current node is null. If so, it returns -1.
     • It recursively calls itself for the left and right children of the current node to calculate their heights.
     • It calculates the current node's height as the maximum of its children's heights plus one.
     • It adds the current node's value to the appropriate sublist in the list of leaves, based on the current node's height. If the sublist for the current height doesn't exist, it creates a new sublist.
     • It returns the current node's height.

2. Find Leaves of the Binary Tree:

   • Define the main function findLeaves that takes the root of the binary tree. This function initializes the list of leaves and calls the dfs function with the root node.
   • The dfs function populates the list with leaves grouped by their removal rounds as it traverses the tree.
   • Finally, the findLeaves function returns the list of leaves.

Algorithm Walkthrough

Let's consider the Input: root = [1,2,3,null,null,4,5,null,null,6,null]

        1
       / \
      2   3
         / \
        4   5
           /
          6  

1. Start DFS with Root Node 1:

   • The root node 1 is not a leaf. We proceed with its children.

2. Traverse to the Left Child 2 of Root Node 1:

   • Node 2 is a leaf node (no children).
   • It's added to leaves[0] since its height from the bottom is 0.
   • The list now looks like [[2]].

3. Backtrack to Node 1 and Traverse to the Right Child 3:

   • Node 3 is not a leaf. We proceed with its children.

4. Traverse to the Left Child 4 of Node 3:

   • Node 4 is a leaf node.
   • It's added to leaves[0], updating the list to [[2, 4]].

5. Traverse to the Right Child 5 of Node 3:

   • Node 5 is not a leaf. We proceed with its child.

6. Traverse to the Left Child 6 of Node 5:

   • Node 6 is a leaf node.
   • It's added to leaves[0], updating the list to [[2, 4, 6]].

7. Backtrack to Node 5 After Removing 6:

   • Now, Node 5 becomes a leaf.
   • It's height from the bottom is 1 (since it was one level above 6).
   • It's added to leaves[1], updating the list to [[2, 4, 6], [5]].

8. Backtrack to Node 3 After Removing Its Children (4 and 5):

   • Node 3 now becomes a leaf.
   • Its height from the bottom is 2.
   • It's added to leaves[2], updating the list to [[2, 4, 6], [5], [3]].

9. Backtrack to Root Node 1 After Removing Its Children:

   • Finally, the root node 1 becomes the last leaf to be removed.
   • Its height from the bottom is 3.
   • It's added to leaves[3], completing the list as [[2, 4, 6], [5], [3], [1]].

Code