DFS with States - Backtracking / Combinatorial Search

Problems
67

Unfortunately i am stuck at the same point. Did you figure it out SF? How serialization of ternary tree works?

68

Really struggling with this concept, can the editors please expand on this section?

69 
def ternary_tree_paths(root: Node) -> List[str]:
    # WRITE YOUR BRILLIANT CODE HERE
    paths = []
    helper_dfs(root, "", paths)
    return paths

def helper_dfs(node, path, paths):
    path += str(node.val)
    
    if not node.children:
        paths.append(path)
        return 
    
    for child in node.children:
        helper_dfs(child, path + "->", paths)
70

hey, we added the step-by-step visualization for the dfs call stack. anything else you donā€™t understand and would like to clarify?

71

the question is essentially the same as the questions in the dfs section. the new thing is the push and pop/space saving part, which we added a visualization. let me know if thereā€™s anything else youā€™d like to see

72

In the python solution if condition is surplus

dfs on each non-null child

    for child in root.children:
        if child is not None:
            dfs(child, path + [str(root.val)], res)
73

I think this ā€˜if all(c is None for c in root.children)ā€™ could be simplified to ā€˜if not root.childrenā€™

74

Before I looked at the included solution, I came up with a short and simple Java one that passes. Updated with a space-saving version that just instantiates one ArrayList.

    public static List<String> ternaryTreePaths(Node<Integer> root) {
        List<String> paths = new ArrayList<>();
        return buildTernaryTreePaths(root, paths, "");
    }
    
    private static List<String> buildTernaryTreePaths(Node<Integer> root, List<String> paths, String path) {
        if (root == null) return paths;
        path = path + root.val;
        if (root.children.size() == 0) {
            paths.add(path);
        }
        for (Node child : root.children) {
            buildTernaryTreePaths(child, paths, path + "->");
        }
        return paths;
    }
76

Hi,

hereā€™s my solution. Lemme know if it is indeed correct,

public static ArrayList<String> dfs(Node<Integer> node, String path, ArrayList<String> result) {
    if (node == null) {
        return result;
    }
    path += node.val;
    if (node.children.isEmpty()) {
        result.add(path);
    } else {
        for (Node<Integer> child : node.children) {
            dfs(child, path+"->", result);
        }
    }
    return result;
}



public static ArrayList<String> ternaryTreePaths(Node<Integer> root) {
    ArrayList<String> res = new ArrayList<String>();
    res = dfs(root, "", res);
    //System.out.println("res is " + res.toString());
    return res;
}
77

For mods, something that could help is to show people how to use the rich text formatting, especially on using the </> button whenever they enter code. Seems like most users donā€™t know

78

Contributing my Java solution that passes the tests and follows similar logic.

public static List<String> ternaryTreePaths(Node<Integer> root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;

        List<String> parentValues = new ArrayList<>();
        ternaryTreePaths(root, paths, parentValues);
        return paths;
    }

    private static void ternaryTreePaths(Node<Integer> root, List<String> paths, List<String> parentVals) {
        parentVals.add(root.val.toString());
        for (AlgoMonsterMultiNode<Integer> child : root.children) {
            ternaryTreePaths(child, paths, parentVals);
        }

        String currentPath = String.join("->", parentVals);
        if (root.children.isEmpty()) { // is leaf
            paths.add(currentPath);
        }
        // remove self
        parentVals.remove(parentVals.size() - 1);
    }

Explanation:
I originally used a Deque#pollLast (this interface was recommended in previous sections) to hold state and behave as a Stack, but ultimately used ArrayList as the Stack instead so that String.join could be compatible with it.

I inadvertently figured out Stacks work well with DFS by doing previous practice problems, but I wish it was actually mentioned as a solution. Ironically Stacks were not really needed until now. I only stumbled upon Stacks as a solution to hold state.

79

Easy to Follow Readble Java Code

public static List<String> ternaryTreePaths(Node<Integer> root) {
            // WRITE YOUR BRILLIANT CODE HERE
        List<String> output = new ArrayList<>();
        dfs(root, new StringBuilder(), output);
        return output;
    }

    public static void  dfs(Node<Integer> root, StringBuilder path, List<String> output){
        // we have reached end path add builder to output exit out recursion
        if (root.children.size() == 0){
            output.add(path.toString());
            return;
        }

        // add node to path 
        path.append(root.val);
        // iter through children recurse through
        for (Node<Integer> child : root.children){
            // make new string builder
            StringBuilder str = new StringBuilder();
            str.append(path).append("->");
            dfs(child, str, output);
        }
        
        
    }
80

Minor tweak to the Alogexpert solution. Found it more readable for a beginner with backtracking like me

def ternary_tree_paths(root: Node) -> List[str]:
    res = []
    def dfs(node, path, res):
        if not node: return
    
        if not node.children:
            res.append('->'.join(path) + '->' + str(node.val))
            return
        
        for child in node.children:
            if child is not None:
                dfs(child, path + [str(node.val)], res)
    res = []
    if root: dfs(root, [], res)
    return res
81

If anyone could provide some feedback on my JS solution, Iā€™d appreciate it.

function ternaryTreePath(root, prePath, paths) {
    if (root.children.length == 0) {
        paths.push(prePath + `${root.val}`);
    }
    
    for (const child of root.children) {
        ternaryTreePath(child, prePath + `${root.val}->`, paths);
    }
}

function ternaryTreePaths(root) {
    const paths = [];
    if (!root || root.children.length == 0) {
        return res;
    }
    
    ternaryTreePath(root, ``, paths);
    return paths;
}

My thought is that since in JS arrays are passed by reference, that I can pass the collecting array all the way down to the leaf nodes, at which point I can push strings into the array.

One large downside I see is that the recursive function isnā€™t a pure function, which I do prefer to write. But it seems like passing the reference is very efficient.

I also feel like constructing a string is more efficient than dealing with an array.

I would really like some feedback - Iā€™m not trying to say that my method is best.

82

My answer is simpler, but it requires that there are no ā€˜Noneā€™ values in the nodeā€™s children list, which suits all the test cases.

def ternary_tree_paths(root: Node) -> List[str]:
    def dfs(node, paths, cur_path):
        if not node.children:
            paths.append('->'.join(cur_path))
            return
        if not cur_path:
            cur_path.append(str(node.val))
        for child in node.children:
            cur_path.append(str(child.val))
            dfs(child, paths, cur_path)
            cur_path.pop()

    paths = []
    dfs(root, paths, [])
    return paths
83

Your way keeps reconstructing the strings over and over again which increases the time complexity

84

The solution with a global variable:

class Solution {
    ...
    private static final List<String> TREE_PATHS = new ArrayList<>();
    
    public static List<String> ternaryTreePaths(Node<Integer> root) {
        if (root == null) return TREE_PATHS;

        dfs(root, "");

        return TREE_PATHS;
    }
    
    private static void dfs(Node<Integer> root, String path) {
        path += root.val;

        if (root.children.isEmpty()) {
            TREE_PATHS.add(path);
        } else {
            for (Node<Integer> child : root.children) {
                dfs(child, path + "->");
            }
        }
    }
}
85

Here is my C++ solution. I think its a little easier to understand

void dfs(Node<int>* root, std::vector<std::string>& res, std::string path = "") {
    if(root->children.empty()){
        res.push_back(path + std::to_string(root->val));
        return;
    }
    
    path.append(std::to_string(root->val) + "->");
    
    for(Node<int>* child : root->children) {
         dfs(child, res, path);
    }
}

std::vector<std::string> ternary_tree_paths(Node<int>* root) {
    if(root == nullptr) return {};
    
    std::vector<std::string> result;
    dfs(root, result);
    
    return result;
}

let me know if you see any issues with it

86

The solution provided is hard to read, here is an alternate:

def ternary_tree_paths(root: Node) -> List[str]:
    def helper(root, path, res):
        if root is None:
            return
        current_path = path + [str(root.val)]
        
        if not root.children:
            res.append('->'.join(current_path))
        else:
            for child in root.children:
                helper(child, current_path, res)
        return res
    result = helper(root,[],[])
    return result
87

Here is my simplified solution

function ternaryTreePaths(root) { 
function dfs(node, currPath, paths) {
    if(!node.children || (node.children.length == 0)) {
        paths.push(currPath.join("->"));
        return;
    }
    node.children.forEach((child) => {
        currPath.push(child.val);
        dfs(child, currPath, paths);
        currPath.pop();
    });
}

let paths = [];
let currPath = [root.val];
dfs(root, currPath, paths);    
return paths;

}