# DFS with States

Prereq: DFS on Tree

Let's reinforce our understanding of state 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

We use `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

``````

## Saving Space

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 ...` `6` `6` `7` `7` `` for child in root.children:`` `8` `8` `` if child is not None:`` `9` `-` `` dfs(child, path + [root.val], res)`` `9` `+` `` path.append(root.val)`` `10` `+` `` dfs(child, path, res)`` `11` `+` `` path.pop()`` `12` `+` `10` `13` `` res = []`` `11` `14` `` if root: dfs(root, [], res)`` `12` `15` `` return res``