Facebook Pixel

DFS with States

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.

Try it yourself

Solution

Define dfs(node, path, res).

path stores the nodes on the current route from the root to node's parent. When we arrive at a leaf, we append node.val to that route, join with "->", and add the string to res.

For each non-null child, we recurse with the updated path that includes the current node value. This means each recursive call has exactly the state it needs: the route taken so far.

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        ArrayList<String> fullPath = new ArrayList<>(path);
5        fullPath.add(Integer.toString(root.val));
6        res.add(String.join("->", fullPath));
7        return;
8    }
9    // DFS on each non-null child
10    for (Node<Integer> child : root.children) {
11        if (child != null) {
12            ArrayList<String> pathCopy = new ArrayList<>(path);
13            pathCopy.add(Integer.toString(root.val));
14            dfs(child, pathCopy, res);
15        }
16    }
17}
18
19public static List<String> ternaryTreePaths(Node<Integer> root) {
20    ArrayList<String> res = new ArrayList<>();
21    if (root != null) dfs(root, new ArrayList<String>(), res);
22    return res;
23}
24
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        const fullPath = [...path, root.val];
5        res.push(fullPath.join('->'));
6        return;
7    }
8    // DFS on each non-null child
9    for (const child of root.children) {
10        if (child) {
11            const path_copy = Array.from(path);
12            path_copy.push(root.val);
13            dfs(child, path_copy, res);
14        }
15    }
16}
17
18function ternaryTreePaths(root) {
19    let res = [];
20    if (root) dfs(root, [], res);
21    return res;
22}
23
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 > 0) {
7                s += "->";
8            }
9            s += path[i];
10        }
11        res.emplace_back(s);
12        return;
13    }
14    for (auto& child: root->children) {
15        if (child) {
16            std::vector<std::string> path_copy(path);
17            path_copy.emplace_back(std::to_string(root->val));
18            dfs(child, path_copy, res);
19        }
20    }
21}
22
23std::vector<std::string> ternary_tree_paths(Node<int>* root) {
24    std::vector<std::string> res;
25    if (root) dfs(root, {}, res);
26    return res;
27}
28
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        List<string> fullPath = new List<string>(path);
7        fullPath.Add(root.val.ToString());
8        res.Add(string.Join("->", fullPath));
9        return;
10    }
11    // DFS on each non-null child
12    foreach (Node<int> child in root.children)
13    {
14        if (child != null)
15        {
16            List<string> pathCopy = new List<string>(path);
17            pathCopy.Add(root.val.ToString());
18            Dfs(child, pathCopy, res);
19        }
20    }
21}
22
23public static List<string> TernaryTreePaths(Node<int> root)
24{
25    List<string> res = new List<string>();
26    if (root != null) Dfs(root, new List<string>(), res);
27    return res;
28}
29
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        fullPath := append(path, strconv.Itoa(root.val))
5        *res = append(*res, strings.Join(fullPath, "->"))
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

The first solution creates a new path object at each recursive step (path + [root.val] or equivalent). That is simple, but it allocates and copies repeatedly.

A more space-efficient version reuses one path list. Before going to a child, push root.val. After returning from that child, pop it. This keeps path synchronized with the call stack.

The rule is strict: every push must have one matching pop in the same stack frame. If you miss a pop, later branches will contain wrong nodes.

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide

Compared with the basic DFS template, we surround each recursive call with push and pop to maintain path state correctly across sibling branches.

Expand 5 lines ...
6
6
7
7
        for child in root.children:
8
8
            if child is not None:
9
-
                
dfs
(
child, path + [
str(root.val)
], res
)
9
+
                
path.append
(
str(root.val)
)
10
+
                dfs(child, path, res)
11
+
                path.pop()
10
12
11
13
    res = []
12
14
    if root: dfs(root, [], res)
Expand 1 lines ...
1
1
private static void dfs(Node<Integer> root, ArrayList<String> path, ArrayList<String> res) {
2
2
    if (root.children.size() == 0) {
3
-
        
ArrayList<String> fullPath = new ArrayList<>
(
path
)
;
3
+
        
path.add
(
Integer.toString(root.val
)
)
;
4
-
        
fullPath
.add(
Integer
.
toString
(
root.val
));
4
+
        
res
.add(
String
.
join
(
"->", path
));
5
-
        
res
.
add
(
String
.
join
(
"->",
 
fullPath
)
)
;
5
+
        
path
.
remove
(
path
.
size
(
)
 
- 1
)
;
6
6
        return;
7
7
    }
8
8
9
9
    for (Node<Integer> child : root.children) {
10
10
        if (child != null) {
11
-
            
ArrayList<String> pathCopy = new ArrayList<>
(
path
)
;
11
+
            
path.add
(
Integer.toString(root.val
)
)
;
12
-
            
pathCopy.add
(
Integer.toString(root.val
)
)
;
12
+
            
dfs
(
child, path, res
)
;
13
-
            
dfs
(
child,
 
pathCopy,
 
res
);
13
+
            
path.remove
(
path.size()
 
-
 
1
);
14
14
        }
15
15
    }
16
16
}
Expand 6 lines ...
1
1
function dfs(root, path, res) {
2
2
    if (root.children.length === 0) {
3
-
        
const fullPath = [...
path
, 
root.val
]
;
3
+
        
path
.push(
root.val
)
;
4
-
        
res
.
push(fullPath.
join('->')
)
;
4
+
        
const cur_path = path
.
join('->')
;
5
+
        res.push(cur_path);
6
+
        path.pop();
5
7
        return;
6
8
    }
7
9
    for (const child of root.children) {
8
10
        if (child) {
9
-
            
const path_copy = Array
.
from
(
path
);
11
+
            
path
.
push
(
root.val
);
10
-
            
path_copy.push
(
root.val
);
12
+
            
dfs
(
child, path, res
);
11
-
            
dfs
(
child, path_copy, res
);
13
+
            
path.pop
(
);
12
14
        }
13
15
    }
14
16
}
Expand 6 lines ...
1
-
void dfs(Node<int>* root, std::vector<std::string
>
 path, std::vector<std::string>& res) {
1
+
void dfs(Node<int>* root, std::vector<std::string
>&
 path, std::vector<std::string>& res) {
2
2
    if (root->children.size() == 0) {
3
3
        path.emplace_back(std::to_string(root->val));
4
4
        std::string s = "";
Expand 4 lines ...
9
9
            s += path[i];
10
10
        }
11
11
        res.emplace_back(s);
12
+
        path.pop_back();
12
13
        return;
13
14
    }
14
15
    for (auto& child: root->children) {
15
16
        if (child) {
16
-
            
std::
vector<std::string> path_copy
(
path
)
;
17
+
            
path.emplace_back(
std::
to_string
(
root->val
)
)
;
17
-
            
path_copy.emplace_back
(
std::to_string(root->val
)
)
;
18
+
            
dfs
(
child, path, res
)
;
18
-
            
dfs
(
child, path_copy, res
);
19
+
            
path.pop_back
(
);
19
20
        }
20
21
    }
21
22
}
22
23
23
24
std::vector<std::string> ternary_tree_paths(Node<int>* root) {
24
25
    std::vector<std::string> res;
25
-
    
if
 
(root) dfs(root, {}, res)
;
26
+
    
std::vector<std::string>
 
path
;
27
+
    if (root)  dfs(root, path, res);
26
28
    return res;
27
29
}
Expand 2 lines ...
3
3
    // exit condition: when a leaf node is reached, append the path to results
4
4
    if (root.children.Count == 0)
5
5
    {
6
-
        
List<string> fullPath = new List<string>
(
path
)
;
6
+
        
path.Add
(
root.val.ToString(
)
)
;
7
-
        
fullPath
.Add(
root
.
val.ToString
(
));
7
+
        
res
.Add(
string
.
Join
(
"->", path
));
8
-
        
res
.
Add
(
string
.
Join("->",
 
fullPath
)
)
;
8
+
        
path
.
RemoveAt
(
path
.
Count
 
- 1
)
;
9
9
        return;
10
10
    }
11
11
    // DFS on each non-null child
Expand 1 lines ...
13
13
    {
14
14
        if (child != null)
15
15
        {
16
-
            
List<string> pathCopy = new List<string>
(
path
)
;
16
+
            
path.Add
(
root.val.ToString(
)
)
;
17
-
            
pathCopy.Add
(
root.val.ToString(
)
)
;
17
+
            
Dfs
(
child, path, res
)
;
18
-
            
Dfs
(
child,
 
pathCopy,
 
res
);
18
+
            
path.RemoveAt
(
path.Count
 
-
 
1
);
19
19
        }
20
20
    }
21
21
}
Expand 7 lines ...
1
-
func dfs(root Node, path 
[]string, res *[]string) {
1
+
func dfs(root Node, path 
*
[]string, res *[]string) {
2
2
    // exit condition: when a leaf node is reached, append the path to results
3
3
    if len(root.children) == 0 {
4
-
        
fullPath
 
:=
 append(
path, strconv.Itoa(root.val))
4
+
        
*path
 
=
 append(
*
path, strconv.Itoa(root.val))
5
-
        *res = append(*res, strings.Join(
fullPath
, "->"))
5
+
        *res = append(*res, strings.Join(
*path
, "->"))
6
+
        *path = (*path)[:len(*path)-1]
6
7
        return
7
8
    }
8
9
    // DFS on each non-null child
9
10
    for _, child := range root.children {
10
-
        
dfs(child,
 
append(
path, strconv.Itoa(root.val))
, res)
11
+
        
*path
 
= 
append(
*
path, strconv.Itoa(root.val))
12
+
        dfs(child, path, res)
13
+
        *path = (*path)[:len(*path)-1]
11
14
    }
12
15
}
13
16
14
17
func ternaryTreePaths(root Node) []string {
15
18
  var result []string
16
-
  dfs(root,
 
[]string
{}, &result)
19
+
    var
 
path 
[]string
20
+
  dfs(root, &path, &result)
17
21
  return result
18
22
}
Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro