DFS with States
Prereq: DFS on Tree
So far in our search, when we visit a node we "do stuff with the current node" but we don't use any information from nodes we have visited before (we don't keep any state). In the following problem, we will see how to carry a state with each dfs call.
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.
def ternary_tree_paths(root): # dfs helper function def dfs(root, path, res): # exit condition, reached leaf node, append paths to results if all(c is None for c in root.children): res.append('->'.join(path) + '->' + root.val) return # dfs on each non-null child for child in root.children: if child is not None: dfs(child, path + [root.val], res) res =  if root: dfs(root, , res) return res
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 copy over each element. A more efficient way is to use a single list and append/pop following the call stack.
Expand 5 lines ...