Prereq: Recursion, DFS on Tree

In DFS, a state is information we pass from a parent call to a child call. In this article, the state is the path from the root to the current node.

Once you can carry this path state correctly, you can solve many backtracking problems by the same pattern: choose, recurse, undo.

Ternary Tree Paths

Given a ternary tree (each node of the tree can have up to three children), find all the root-to-leaf paths.