Simple traversal

Complexity -

Worst Case - assume tree is slanted either to right or left, each time leaf is popped, a size of tree reduces by 1, so

T(n) = n + n-1 + n-2 .... + 1 = n(n+1)/2 = O(n^2)

Best Case - tree is complete balanced binary tree, each time leaves are popped size reduces by half

T(n) = n + n/2 + n/4 + ..... = O ( n*log(n) )

class TreeNode(object):
def __init__(self,val):
self.val = val
self.left = self.right = None
def popLeaves(node,leaves):
if node:
if node.left is None and node.right is None:
leaves.append(node.val) # node is a leaf, save it in a list
return None # unlinking it from tree
else:
# node is internal node
node.left = popLeaves(node.left, leaves)
node.right = popLeaves(node.right, leaves)
return node
def purge(root):
result = []
while root:
leaves = []
root = popLeaves(root,leaves) # pop leaves in current state of a tree
result.append(leaves[:]) # put all collected leaves in a result
print(result)
return result