DFS with States
Prereq: Recursion, DFS on Tree
Let's reinforce our understanding of the idea of the "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
Solution
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.
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
1private static void dfs(Node<Integer> root, ArrayList<String> path, ArrayList<String> res) {
2 // exit condition, reached leaf node, append paths to results
3 if (root.children.size() == 0) {
4 path.add(Integer.toString(root.val));
5 res.add(String.join("->", path));
6 return;
7 }
8 // dfs on each non-null child
9 for (Node<Integer> child : root.children) {
10 if (child != null) {
11 ArrayList<String> pathCopy = new ArrayList<>(path);
12 pathCopy.add(Integer.toString(root.val));
13 dfs(child, pathCopy, res);
14 }
15 }
16}
17
18public static List<String> ternaryTreePaths(Node<Integer> root) {
19 ArrayList<String> res = new ArrayList<>();
20 if (root != null) dfs(root, new ArrayList<String>(), res);
21 return res;
22}
23
1function dfs(root, path, res) {
2 // exit condition, reached leaf node, append paths to results
3 if (root.children.length === 0) {
4 path.push(root.val);
5 const cur_path = path.join('->');
6 res.push(cur_path);
7 return;
8 }
9 // dfs on each non-null child
10 for (const child of root.children) {
11 if (child) {
12 const path_copy = Array.from(path);
13 path_copy.push(root.val);
14 dfs(child, path_copy, res);
15 }
16 }
17}
18
19function ternaryTreePaths(root) {
20 let res = [];
21 if (root) dfs(root, [], res);
22 return res;
23}
24
1void dfs(Node<int>* root, std::vector<std::string> path, std::vector<std::string>& res) {
2 if (root->children.size() == 0) {
3 path.emplace_back(std::to_string(root->val));
4 std::string s = "";
5 for (int i = 0; i < path.size(); i++) {
6 if (i == path.size() - 1) {
7 s += path[i];
8 } else {
9 s += path[i] + "->";
10 }
11 }
12 res.emplace_back(s);
13 return;
14 }
15 for (auto& child: root->children) {
16 if (child) {
17 std::vector<std::string> path_copy(path);
18 path_copy.emplace_back(std::to_string(root->val));
19 dfs(child, path_copy, res);
20 }
21 }
22}
23
24std::vector<std::string> ternary_tree_paths(Node<int>* root) {
25 std::vector<std::string> res;
26 if (root) dfs(root, {}, res);
27 return res;
28}
29
1private static void Dfs(Node<int> root, List<string> path, List<string> res)
2{
3 // exit condition: reached leaf node, append paths to results
4 if (root.children.Count == 0)
5 {
6 path.Add(root.val.ToString());
7 res.Add(string.Join("->", path));
8 return;
9 }
10 // dfs on each non-null child
11 foreach (Node<int> child in root.children)
12 {
13 if (child != null)
14 {
15 List<string> pathCopy = new List<string>(path);
16 pathCopy.Add(root.val.ToString());
17 Dfs(child, pathCopy, res);
18 }
19 }
20}
21
22public static List<string> TernaryTreePaths(Node<int> root)
23{
24 List<string> res = new List<string>();
25 if (root != null) Dfs(root, new List<string>(), res);
26 return res;
27}
28
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 copying over each element. A more efficient way is to use a single list path
and push
and pop
following the call stack.
Feel free to check back recursion section if you need a review of call stack.
Expand 5 lines ... | |||||
6 | 6 | ||||
7 | 7 |
| |||
8 | 8 |
| |||
9 | - |
| |||
9 | + |
| |||
10 | + |
| |||
11 | + |
| |||
12 | + | ||||
10 | 13 |
| |||
11 | 14 |
| |||
12 | 15 |
|
Expand 1 lines ... | |||||
2 | 2 |
| |||
3 | 3 |
| |||
4 | 4 |
| |||
5 | + |
| |||
5 | 6 |
| |||
6 | 7 |
| |||
7 | 8 | ||||
8 | 9 |
| |||
9 | 10 |
| |||
10 | - |
| |||
11 | + |
| |||
11 | - |
| |||
12 | + |
| |||
12 | - |
| |||
13 | + |
| |||
13 | 14 |
| |||
14 | 15 |
| |||
15 | 16 |
| |||
16 | 17 | ||||
17 | 18 |
| |||
Expand 4 lines ... |
Expand 2 lines ... | |||||
3 | 3 |
| |||
4 | 4 |
| |||
5 | 5 |
| |||
6 | + |
| |||
6 | 7 |
| |||
7 | 8 |
| |||
8 | 9 |
| |||
9 | 10 |
| |||
10 | - |
| |||
11 | + |
| |||
11 | - |
| |||
12 | + |
| |||
12 | - |
| |||
13 | + |
| |||
13 | 14 |
| |||
14 | 15 |
| |||
15 | 16 |
| |||
16 | 17 | ||||
17 | 18 |
| |||
Expand 4 lines ... |
Expand 9 lines ... | |||||
10 | 10 |
| |||
11 | 11 |
| |||
12 | 12 |
| |||
13 | + |
| |||
13 | 14 |
| |||
14 | 15 |
| |||
15 | 16 |
| |||
16 | 17 |
| |||
17 | - |
| |||
18 | + |
| |||
18 | - |
| |||
19 | + |
| |||
19 | - |
| |||
20 | + |
| |||
20 | 21 |
| |||
21 | 22 |
| |||
22 | 23 |
| |||
23 | 24 | ||||
24 | 25 |
| |||
Expand 1 lines ... | |||||
26 | - |
| |||
27 | + |
| |||
27 | 28 |
| |||
28 | 29 |
|
Expand 4 lines ... | |||||
5 | 5 |
| |||
6 | 6 |
| |||
7 | 7 |
| |||
8 | + |
| |||
8 | 9 |
| |||
9 | 10 |
| |||
10 | 11 |
| |||
Expand 1 lines ... | |||||
12 | 13 |
| |||
13 | 14 |
| |||
14 | 15 |
| |||
15 | - |
| |||
16 | + |
| |||
16 | - |
| |||
17 | + |
| |||
17 | - |
| |||
18 | + |
| |||
18 | 19 |
| |||
19 | 20 |
| |||
20 | 21 |
| |||
21 | 22 | ||||
22 | 23 |
| |||
Expand 5 lines ... |
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.