Return every root-to-leaf path in the tree, each as a slice of values from root to leaf. Order the paths by a left-to-right depth-first traversal.
allTreePaths(root)
Input format: level-order with x for missing children. Output each path's
values joined by -, with paths separated by spaces (e.g. 1-2 1-3).
1 2 3 // → [[1 2] [1 3]] → "1-2 1-3"
3 9 20 x x 15 7 // → [[3 9] [3 20 15] [3 20 7]]
5 // → [[5]] → "5"
This extends single-path-finding into finding every root-to-leaf path at once. Every leaf defines exactly one path, and every path ends at exactly one leaf, so the number of paths equals the number of leaves.
For any node: what are all the root-to-leaf paths starting here? If this node is a leaf, there's exactly one: itself. If it has children, every path starting here continues into a child, so the paths from here are the left subtree's paths plus the right subtree's paths, each with this node's value stuck onto the front.
Unlike tree-sum or tree-node-count, where each child contributes one number combined into one number, here each child can contribute multiple paths, none combined into each other — they all survive independently. So combining means concatenation, not addition: gather every path from the left, every path from the right, and prepend this node's value to each individually.
Each call only knows about its own subtree — it has no way to know what came before it in the full path from the true root. That only becomes available as the recursion unwinds. So each level attaches its own value to the front of whatever its children already assembled, and by the time the outermost call returns, every path has the correct root-to-leaf order.
Since paths need to come out ordered by a left-to-right depth-first traversal, gathering the left subtree's paths before the right's at every level preserves that order recursively — no separate sort needed.
Each path can be as long as the tree's height, and there can be as many paths as leaves, so building all of them costs time proportional to their combined length — worst case, proportional to the number of nodes times the tree's height for a very unbalanced tree.
def all_tree_paths(root):
if root is None:
return []
if root.left is None and root.right is None:
return [[root.val]]
paths = []
subs = all_tree_paths(root.left) + all_tree_paths(root.right)
for sub in subs:
paths.append([root.val] + sub)
return paths
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.