Problem Statement in English
Given the root of a binary tree, collect a tree’s nodes as if you were doing this:
- Collect all the leaf nodes.
- Remove all the leaf nodes.
- Repeat until the tree is empty.
The order in which you collect the leaves doesn’t matter, just the order of the levels.
Approach
If we had some way to reliably determine the height of a node such that all initial leaves are the same height initally we can apply that to all other nodes and correctly classify them as well.
One such method here is to mark the leaves as height $-1$ and then for its parent, we propagate 1 plus that height. Since the parent may receive 2 different heights from its children, we take the maximum of the two.
When we get that height, we can store all nodes with the same height in a dictionary and return the values of that dictionary as a list.
Solution in Python
class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
pairs = defaultdict(list)
def height(node):
if not (node.left or node.right):
pairs[-1].append(node.val)
return 0
leftHeight = rightHeight = 0
if node.left:
leftHeight = height(node.left)
if node.right:
rightHeight = height(node.right)
thisHeight = max(leftHeight, rightHeight)
pairs[thisHeight].append(node.val)
return thisHeight + 1
height(root)
return list(pairs.values())
Complexity
Time: $O(n)$
Since we are visiting each node once, the time complexity is linear in the number of nodes in the tree.Space: $O(n)$
We are storing all the nodes in a dictionary, which will take linear space in the number of nodes in the tree.
Mistakes I Made
I had to look this up :(
And we are done.