My code was just a tad different by not having the all in the base condition…
def ternary_tree_paths(root: Node) → List[str]:
# WRITE YOUR BRILLIANT CODE HERE
res = []
local = [str(root.val)]
return dfs(root, res, local)
def dfs(root, res, local):
if not root.children:
res.append(‘->’.join(local))
return
for child in root.children:
local.append(str(child.val))
dfs(child, res, local)
local.pop()
return res
For C++ solution, you loop through refernces and do
if (child)
References are never null, and you would get an exception in this case. its not a good code. It doesnt compile for me.
Of course had to make changes, which is fine
Ability to provide a debugger within the solution terminal would be great!
I have more simple version in C++
void paths_helper(Node *root, std::string path, std::vectorstd::string &result)
{
if (!root) {
return;
}
path += std::to_string(root->val);
if (root->children.empty()) {
result.emplace_back(path);
} else {
path += "->";
for (auto child: root->children) {
paths_helper(child, path, result);
}
}
}
std::vectorstd::string ternary_tree_paths(Node* root) {
std::vectorstd::string result;
paths_helper(root, {}, result);
return result;
}
one thing I really didn’t understand was the purpose on path.pop(). but I figured it out.
if we removed all the path.pop(), you will see that path only becomes additive. in each iteration of a loop, path is not reset, when we feed our path value into the next child, it will alter the path value of the earlier iteration. the next child, will change the path value for the previous parent node.
to demonstrate clearly try 2 things:
1.) remove all .pop() and console.log(path) after each .push(root.val) in both the loop and the if statement. you will see that path simply adds values on.
2.) add a console.log(path) after each .push(root.val) AND after each .pop() in the loop and if statement. you will see that as we go down the children, it becomes additive, growing our path until we arrive at the end. but as we traverse back up, we reset to an empty array at the highest level of our tree, 1 pop at a time back.
why not just reset path = []? because if we have a ternary tree where the children of the root node have multiple children as well, then their path’s would end up starting at the previous node, completely forgetting the previous path to get there from the root node. so, we only want to pop one at a time, so that each child of each node remember the previous path.
For the first solution you provide, I find it is unnecessary to make res a paramenter for recursive call. Would it be better if we set res a global variable?
Either way works. See the detailed discussion here https://algo.monster/problems/dfs_on_trees_intro
def ternary_tree_paths(root: Node) → List[str]:
# WRITE YOUR BRILLIANT CODE HERE
totalpaths = []
stack = [(root,[root])]
visited = []
while stack:
curr_node,path = stack.pop()
#if we reach the laf node, then we need to add the current path to all paths
if curr_node and not curr_node.children:
totalpaths.append(path)
continue
if curr_node in visited:
continue
visited.append(curr_node)
#add the children with larger values to smaller values
childrs = curr_node.children[::-1]
for child in childrs:
stack.append((child,path + [child]))
output = []
for path in totalpaths:
temp =“”
for i,p in enumerate(path):
temp += str(p.val)
if i != len(path)-1:
temp +=“->”
output.append(temp)
return output
in second solution
I believe there is no need of adding to path and removing from path inside for loop. It can be only done once
private static void dfs(Node<Integer> root, List<String> path, List<String> res) {
// exit condition, reached leaf node, append paths to results
if (root.children.size() == 0) {
path.add(Integer.toString(root.val));
res.add(String.join("->", path));
path.remove(path.size() - 1);
return;
}
// add to path current node value
path.add(Integer.toString(root.val));
// dfs on each non-null child
for (Node<Integer> child : root.children) {
dfs(child, path, res);
}
// remove from path once we are returning from this node
path.remove(path.size() - 1);
}
I’m having hard time understanding how the serialization of the tree is equal to ‘1 3 2 1 3 0 4 0 6 0’?
I got it now.
I have 2 different interesting solutions.
The 1st looks like the given one but is simpler:
void ttp(Node* root, std::string path, std::vectorstd::string& res) {
if (!root) return;
if (!path.empty()) path.append("->");
path.append(std::to_string(root->val));
if (root->children.empty()) {
res.push_back(path);
return;
}
for (const auto& child : root->children) {
ttp(child, path, res);
}
}
std::vectorstd::string ternary_tree_paths(Node* root) {
std::vectorstd::string paths;
ttp(root, “”, paths);
return paths;
}
The 2nd creates paths string from the end:
std::vectorstd::string ternary_tree_paths(Node* root) {
if (!root) return {};
std::vector<std::string> paths;
for (const auto& child : root->children) {
const std::vector<std::string>& temp = ternary_tree_paths(child);
paths.reserve(paths.size() + temp.size());
paths.insert(paths.end(), temp.begin(), temp.end());
}
std::string val_str = std::to_string(root->val);
if (paths.empty())
paths.push_back(val_str);
else {
val_str.append("->");
for (std::string& path : paths) {
path.insert(0, val_str);
}
}
}
What is the difference between “path + [str(root.val)]” and “path.append(str(root.val))” in the second solution. Do those not accomplish the same thing?
For the python solution, if the tree contains only 1 node
Input 1 0
Output will be → 1, I think it is weird, for Java and C++ solution
it will output 1. Need to update python solution ?
Another C# solution using yield pattern.
public static List<string> TernaryTreePaths(Node<int> root)
{
return TraversePaths(root).ToList();
}
public static IEnumerable<string> TraversePaths(Node<int> node)
{
if(node == null)
{
yield break;
}
if (node.children.Count == 0)
{
yield return node.val.ToString();
}
foreach(var child in node.children)
{
foreach(var childPath in TraversePaths(child))
{
yield return string.Join("->", node.val.ToString(), childPath);
}
}
}
yes, “path + [str(root.val)]” makes a copy which is wasteful therefore the second solution uses “path.append(str(root.val))”
Structured Programming JS Solution:
function ternaryTreePaths(root) {
let result = [];
if (root.children.length > 0) {
for (const child of root.children) {
if (child) {
const res = ternaryTreePaths(child);
res.forEach((r) => result.push(`${root.val}->${r}`));
}
}
} else {
result.push(`${root.val}`);
}
return result;
}
Not clear why do we need the state at all. Wouldn’t this be simpler?
def find_paths(root: Node) → List[str]:
answers = []
if not root.children:
return [[str(root.val)]]
for child in root.children:
paths = find_paths(child)
for path in paths:
answers.append([str(root.val)] + path)
return answers
def ternary_tree_paths(root: Node) → List[str]:
answers = find_paths(root)
return ["->".join(answer) for answer in answers]
That works too. The problem is meant to demonstrate the push and pop ops to make intro for the backtracking template in the next article.
Your solution is essentially using the ‘using return value’ approach in https://algo.monster/problems/dfs_on_trees_intro
Sorry, but the link provided shows serialisation of a binary tree. It is not clear for me how to jump from the serialisation of a binary tree to such of a generic one.
This section could have much more information! not just two lines of text and “now do the solution”