DFS with States
Prereq: DFS on Tree
Let's reinforce our understanding of the idea of states with one more example.
Ternary Tree Paths
Given a ternary tree (each node of the tree has at most three children), find all root-to-leaf paths.
Try it yourself
path to keep track of the nodes we have visited to reach the current node and use it to construct our solution when we reach leaf nodes.
1def ternary_tree_paths(root): 2 # dfs helper function 3 def dfs(root, path, res): 4 # exit condition, reached leaf node, append paths to results 5 if all(c is None for c in root.children): 6 res.append('->'.join(path) + '->' + str(root.val)) 7 return 8 9 # dfs on each non-null child 10 for child in root.children: 11 if child is not None: 12 dfs(child, path + [str(root.val)], res) 13 14 res =  15 if root: dfs(root, , res) 16 return res 17
In the recursive call in the previous solution, we create a new list each time we recurse with
path + [root.val]. This is not space-efficient because creating a new list requires allocating new space in memory and copying over each element. A more efficient way is to use a single list and append/pop following the call stack.
Expand 5 lines ...