DFS with States - Backtracking / Combinatorial Search

Problems
22

Update: I figured out the bug in your C# template. You’re Console.WriteLine’ing “res” instead of “line”.

23

Thank you for pointing out. We’ve fixed it.

24

I wish there was more explanation of the expected output before asking you to solve it yourself, it’s not clear you’re expected to return a string or an array or what. So I have to look at the solution before trying

1 Like
25

Why the solution for Python and Java is so different?

28

Hmmm, looks like you don’t actually need to pass ‘res’ as a parameter to the dfs function since it’s a global variable. Trying with dfs(root, path) passes all the test cases too.

29

For C++
ternary_tree_paths(Node root) should accept a pointer/reference instead of the object.
And the build_tree should return a Node* instead of Node

30

function ternaryTreePaths(root) {
const result = [];
dfs(root, ${root.val}, result);

return result;

}

const dfs = (root, path, result) => {
if(!root) return;

if(root.children.length === 0) {
    result.push(path);
    return;
}

for(const child of root.children) {
    dfs(child, `${path}->${child.val}`, result);
}

};

31

Why do this?

if(root.children.every(child => !child)) { … }

instead of this?

if(root.children.length === 0) { … }

32

Completely agree

33

Hi, talk about my feelings.
“Binary Search” chapter, the material is good for understand and practise. When I into “Depth First Search”, especially from this sub-section “Balanced Binary Tree”, it’s hard to understand but less explation, makes me struggle. this article is ‘simplicity’ too.
Maybe my data structure foundation is not very good, if could add some recommended reading material or more detailed explanation would be better

1 Like
34

the comment system need improve readability and code formatting :grinning:

35

In Java, why does the function in the solution return the Array while in the “Try yourself” section, it returns List?

36

Wow, this MOD just said it’s going to pass the test without even confirming and silently fixed the test after 2 weeks??? very respectful

37

The question and the solution don’t have the same return type lolol. Started noticing AlgoMonster is pretty disorganized. Won’t recommend it to anyone anymore.

38

A C# version:

public static List<string> TernaryTreePaths(KNode<int> node){

    List<string> paths = new List<string>();
    _ternaryTreePaths(node, "");
    return paths;

    void _ternaryTreePaths(KNode<int> node, string path){

        path += $"{node.val.ToString()}->";

        if (node.children == null || node.children.Count() == 0){
            path = path.Substring(0, path.Length - 2);
            paths.Add(path);
            return;
        }

        foreach(var childNode in node.children){
            _ternaryTreePaths(childNode, path);
        }
    }
}
39

Sorry about the KNode (its the same as the Node class in the standard examples here)

40

Alternative implementation in Java (state carried up only as as part of return value):

public static List<String> ternaryTreePaths(Node<Integer> root) {
    if (root==null) return List.of();        
    Integer val=root.val;
    List<String> result = new LinkedList<String>();
    if(root.children==null || root.children.size() == 0)
        result.add(val+"");
    for(Node<Integer> chld: root.children) {
        List<String> chldRes = ternaryTreePaths(chld);
        for(String s: chldRes) {
            String withP = val+"->"+s;
            result.add(withP);
        }            
    }
    return result;
}
41

Why to use path.pop()? I didn’t understand.

42

Do you mean why using append and pop?

In the first solution, path + [root.val] creates a new list for each recursive call which takes much space. In the second solution,append and pop operates on the same list and the list (reference) gets passed as function argument for each recursive calls so there’s only one list.

43

This path + [root.val] is tricky.
In dfs(child, path + [root.val], res) call, it will pass a new value of path, aka “path + [root.val]” to the next recursive call.
However, here’s the tricky part, after that recursive call is finished and returned, the “path” will be ‘restored’ to the original value.
Give you an example:
path = [1, 2, 3]
then dfs(child, path + [4], res) will pass [1,2,3,4] to the next dfs call,
after this dfs(…) is done, path will still be [1,2,3]. You can add prints before and after for verification.

So, if we don’t use path + [root.val], and if we update path before dfs() call, like this:
path.append(root.val)
After the dfs() call, we need to restore the original path, that’s why we need
path.pop()