I am currently stuck with a problem that when I started out seemed not too hard to solve for me, but I am stuck for a couple of hours now, so here we go:
Given this nested objects/tree:
const tree = {
value: 50, children: [
{
value: 17, children: [
{
value: 12, children:
[
{ value: 9, children: null },
{ value: 14, children: null }
]
},
{ value: 23, children: null }
]
}, {
value: 72, children: [
{
value: 54, children: [
{
value: 67, children: null
}
]
},
{
value: 76, children: null
}
]
}
],
}
I am trying to find a function that gives me the path to a value
function findPath(tree, target){
...
}
and the function will return something like
findPath(tree, 67);
<==============>
[50, 72, 54, 67]
I'm new to code. I hope I'll get you help to solve this. Thanks.
One option with trees is recursion. Recursively search children until the value is found. On the way back up, build the array. Not sure this is the most efficient but it works.
const tree = {
value: 50,
children: [{
value: 17,
children: [{
value: 12,
children: [{
value: 9,
children: null
},
{
value: 14,
children: null
}
]
},
{
value: 23,
children: null
}
]
}, {
value: 72,
children: [{
value: 54,
children: [{
value: 67,
children: null
}]
},
{
value: 76,
children: null
}
]
}],
};
function findPath(tree, target) {
// The value of this node
let currentValue = tree.value;
if (currentValue == target) return [target];
for (let t of Object.entries(tree)) {
// Search children
if (t[0] == "children" && t[1]) {
for (let child of t[1]) {
let found = findPath(child, target);
if (found) {
return [currentValue].concat(found);
}
}
}
}
// Not found in this branch
return null;
}
console.log(findPath(tree, 67));You can use recursion to find the path (see comments in code):
function findPath({ value, children }, target) {
if(value === target) return [value] // if the value is found return it wrap in an array
for(const child of children ?? []) { // iterate the children or an empty array
const leaf = findPath(child, target) // use findPath on all children
if(leaf) return [value, ...leaf] // if a leaf is found (not null) spread it to the current array, and return it
}
return null
}
const tree = {"value":50,"children":[{"value":17,"children":[{"value":12,"children":[{"value":9,"children":null},{"value":14,"children":null}]},{"value":23,"children":null}]},{"value":72,"children":[{"value":54,"children":[{"value":67,"children":null}]},{"value":76,"children":null}]}]}
const result = findPath(tree, 67)
console.log(result)Here's a solution using depth-first search, a tree traversal algorithm.
function findPath(tree, target) {
const path = [];
const stack = [tree];
while (stack.length) {
let curr = stack.pop();
path.push(curr.value);
if (curr.value === target) return path;
if (curr.children !== null) {
curr.children.forEach(child => stack.push(child));
} else {
path.pop();
}
}
// target not found
return [];
}
const tree = {"value":50,"children":[{"value":17,"children":[{"value":12,"children":[{"value":9,"children":null},{"value":14,"children":null}]},{"value":23,"children":null}]},{"value":72,"children":[{"value":54,"children":[{"value":67,"children":null}]},{"value":76,"children":null}]}]};
console.log(findPath(tree, 67));