DFS with States

Prereq: Recursion, DFS on Tree

Let's reinforce our understanding of the concept of "states" with another example.

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.

Try it yourself

Solution

We use path to keep track of the nodes we have visited so far to reach the current node and use it to construct our solution when we reach the leaf nodes.

1def ternary_tree_paths(root):
2    # dfs helper function
3    def dfs(root, path, res):
4        # exit condition: when a leaf node is reached, append the path to the 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: when a leaf node is reached, append the path to the 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: when a leaf node is reached, append the path to the 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: when a leaf node is reached, append the path 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
1func dfs(root Node, path []string, res *[]string) {
2    // exit condition: when a leaf node is reached, append the path to results
3    if len(root.children) == 0 {
4        path = append(path, strconv.Itoa(root.val))
5        *res = append(*res, strings.Join(path, "->"))
6        return
7    }
8
9    // DFS on each non-null child
10    for _, child := range root.children {
11        dfs(child, append(path, strconv.Itoa(root.val)), res)
12    }
13}
14
15func ternaryTreePaths(root Node) []string {
16  var result []string
17  dfs(root, []string{}, &result)
18  return result
19}
20

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 involves allocating new space in memory and copying over each element. A more efficient method is to use a single list, path, and push and pop according to the call stack. Feel free to revisit the recursion section if you need a review of the 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 ...
1
-
1func dfs(root Node, path []string, res *[]string) {
1
+
1func dfs(root Node, path *[]string, res *[]string) {
2
2
1    // exit condition: when a leaf node is reached, append the path to results
3
3
1    if len(root.children) == 0 {
4
-
1        path = append(path, strconv.Itoa(root.val))
4
+
1        *path = append(*path, strconv.Itoa(root.val))
5
-
1        *res = append(*res, strings.Join(path, "->"))
5
+
1        *res = append(*res, strings.Join(*path, "->"))
6
+
1        *path = (*path)[:len(*path)-1]
6
7
1        return
7
8
1    }
8
9
1    // DFS on each non-null child
9
10
1    for _, child := range root.children {
10
-
1        dfs(child, append(path, strconv.Itoa(root.val)), res)
11
+
1        *path = append(*path, strconv.Itoa(root.val))
12
+
1        dfs(child, path, res)
13
+
1        *path = (*path)[:len(*path)-1]
11
14
1    }
12
15
1}
13
16
14
17
1func ternaryTreePaths(root Node) []string {
15
18
1  var result []string
16
-
1  dfs(root, []string{}, &result)
19
+
1    var path []string
20
+
1  dfs(root, &path, &result)
17
21
1  return result
18
22
1}
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.
←
↑TA 👨‍🏫