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.

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
Expand 5 lines ...
6
6
7
7
1        for child in root.children:
8
8
1            if child is not None:
9
-
1                dfs(child, path + [str(root.val)], res)
9
+
1                path.append(str(root.val))
10
+
1                dfs(child, path, res)
11
+
1                path.pop()
12
+
10
13
1    res = []
11
14
1    if root: dfs(root, [], res)
12
15
1    return res
Expand 1 lines ...
2
2
1    if (root.children.size() == 0) {
3
3
1        path.add(Integer.toString(root.val));
4
4
1        res.add(String.join("->", path));
5
+
1        path.remove(path.size() - 1);
5
6
1        return;
6
7
1    }
7
8
8
9
1    for (Node<Integer> child : root.children) {
9
10
1        if (child != null) {
10
-
1            ArrayList<String> pathCopy = new ArrayList<>(path);
11
+
1            path.add(Integer.toString(root.val));
11
-
1            pathCopy.add(Integer.toString(root.val));
12
+
1            dfs(child, path, res);
12
-
1            dfs(child, pathCopy, res);
13
+
1            path.remove(path.size() - 1);
13
14
1        }
14
15
1    }
15
16
1}
16
17
17
18
1public static List<String> ternaryTreePaths(Node<Integer> root) {
Expand 4 lines ...
Expand 2 lines ...
3
3
1        path.push(root.val);
4
4
1        const cur_path = path.join('->');
5
5
1        res.push(cur_path);
6
+
1        path.pop();
6
7
1        return;
7
8
1    }
8
9
1    for (const child of root.children) {
9
10
1        if (child) {
10
-
1            const path_copy = Array.from(path);
11
+
1            path.push(root.val);
11
-
1            path_copy.push(root.val);
12
+
1            dfs(child, path, res);
12
-
1            dfs(child, path_copy, res);
13
+
1            path.pop();
13
14
1        }
14
15
1    }
15
16
1}
16
17
17
18
1function ternaryTreePaths(root) {
Expand 4 lines ...
Expand 9 lines ...
10
10
1            }
11
11
1        }
12
12
1        res.emplace_back(s);
13
+
1        path.pop_back();
13
14
1        return;
14
15
1    }
15
16
1    for (auto& child: root->children) {
16
17
1        if (child) {
17
-
1            std::vector<std::string> path_copy(path);
18
+
1            path.emplace_back(std::to_string(root->val));
18
-
1            path_copy.emplace_back(std::to_string(root->val));
19
+
1            dfs(child, path, res);
19
-
1            dfs(child, path_copy, res);
20
+
1            path.pop_back();
20
21
1        }
21
22
1    }
22
23
1}
23
24
24
25
1std::vector<std::string> ternary_tree_paths(Node<int>* root) {
Expand 1 lines ...
26
-
1    if (root) dfs(root, {}, res);
27
+
1    if (root)  dfs(root, {}, res);
27
28
1    return res;
28
29
1}
Expand 4 lines ...
5
5
1    {
6
6
1        path.Add(root.val.ToString());
7
7
1        res.Add(string.Join("->", path));
8
+
1        path.RemoveAt(path.Count - 1);
8
9
1        return;
9
10
1    }
10
11
1    // dfs on each non-null child
Expand 1 lines ...
12
13
1    {
13
14
1        if (child != null)
14
15
1        {
15
-
1            List<string> pathCopy = new List<string>(path);
16
+
1            path.Add(root.val.ToString());
16
-
1            pathCopy.Add(root.val.ToString());
17
+
1            Dfs(child, path, res);
17
-
1            Dfs(child, pathCopy, res);
18
+
1            path.RemoveAt(path.Count - 1);
18
19
1        }
19
20
1    }
20
21
1}
21
22
22
23
1public static List<string> TernaryTreePaths(Node<int> root)
Expand 5 lines ...
Still not clear? Submit the part you don't understand to our editors.