Return the values of all the leaves (nodes with no children), in left-to-right order.
leafList(root)
Input format: level-order with x for missing children. Output the leaf values
space-separated.
3 9 20 x x 15 7 // → 9 15 7
1 2 3 // → 2 3
5 // → 5
(empty) // → (empty)
A leaf is defined structurally — no left child and no right child — so spotting one just means checking whether both children are absent. The real content of this problem is collecting all such nodes across the tree, in left-to-right order.
For any node: what are all the leaves reachable from here? Two cases. If this node has no children, it's a leaf — return a single-element list containing its own value. If it has at least one child, it isn't a leaf itself, so its own value doesn't belong in the output — every leaf reachable from here comes from further down.
Like all-tree-paths (and unlike tree-sum), each child can contribute any number of leaves, none merged into a single value — they all survive as individual entries. A node's leaf list is simply its left subtree's leaves followed by its right subtree's, laid end to end.
Since you fully gather the left subtree's leaves before starting the right, and this holds recursively at every node, the leftmost leaf overall always appears before the rightmost, however unevenly the tree is shaped. No position-tracking or sorting needed afterward — the traversal order alone guarantees it.
Unlike tree-value-count or tree-includes, whether a node belongs in the output here depends purely on structure (does it have children), not on comparing values. Some tree problems filter by shape, others by content — worth noticing which kind you're facing.
Every node is visited once to check whether it's a leaf, so work is proportional to the number of nodes, with recursion memory bounded by the tree's height.
def leaf_list(root):
if root is None:
return []
if root.left is None and root.right is None:
return [root.val]
return leaf_list(root.left) + leaf_list(root.right)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.