My tree data structure has a unique layout:
[
{
info: object,
children:
[ ...other objects... ]
},
...other objects...
]
The structure can vary in its shape and number of nodes.
I have developed a method that recursively identifies and retrieves the path (an array of intermediate objects) between the root r and a specific object o. (it does not matter whether r and o are included)
public getPath(tree: Array<object>, o: object): Array<object> {
let path: Array<object> = [];
function explore(subtree: Array<object>): void {
for (let node of subtree) {
path.push(node['info']);
if (node['info'] == o) return;
else if (node['children'].length > 0) explore(node['children']);
else path = [];
}
}
explore(tree);
return path;
}
Essentially, my strategy involves:
- Adding every visited object to the array during traversal from r to o,
- Resetting the array if a different path than r to o is encountered,
- Ending the process when reaching o where traversal concludes.
Results:
- This method successfully returns [r] when r is specified as o.
- It also provides the correct path [r, first child of r] when the first child of r is selected as o.
- However, choosing any other object as o results in returning objects beyond the desired path along with those on the correct route.