CODEWITHSUNDEEP
javascriptarraystypescriptrecursionecmascript-6
josh_boaz
josh_boaz

Reputation: 2023

How to find a tree inside a tree in typescript

let say i have a tree in javascript

a1 
--b
----c1
a2
--b2
--b3
----c2

and if i wanted to find c2, it should return a2->b3->c2

Lets say my json looked like this?

treeFamily = {
            name : "Parent",
            children: [{
                name : "Child1",
                children: [{
                    name : "Grandchild1",
                    children: []
                },{
                    name : "Grandchild2",
                    children: []
                },{
                    name : "Grandchild3",
                    children: []
                }]
            }, {
                name: "Child2",
                children: []
            }]
        };

Upvotes: 0

Views: 761

Answers (2)

Ori Drori
Ori Drori

Reputation: 191976

You can use for...of to search the children by calling the function recursively. If the target is found, the name is returned, and combined with the previous names. If not, the function will return undefined. Alternatively, you can return an empty array.

const findPath = (targetName, { name, children }) => {
  if(name === targetName) return [name];
  
  for(const child of children) {
    const result = findPath(targetName, child);
    if(result) return [name, ...result];
  }
  
  // if child not found implicitly return undefined or return [] to get an empty array
};

const treeFamily = { name: "Parent", children: [{ name: "Child1", children: [{ name: "Grandchild1", children: [] }, { name: "Grandchild2", children: [] }, { name: "Grandchild3", children: [] }] }, { name: "Child2", children: [] }] };

console.log(findPath('Child2', treeFamily));
console.log(findPath('Grandchild3', treeFamily));
console.log(findPath('Grandchild400', treeFamily));

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386604

You could check if the nested children have the wanted key/value. Then take the name and hand over the result to the outer call.

function findPath(array, target) {
    var path;
    array.some(({ name, children }) => {
        var temp;
        if (name === target) {
            path = [name];
            return true;
        }
        if (temp = findPath(children, target)) {
            path = [name, ...temp];
            return true;
        }
    });
    return path;
}

var treeFamily = { name: "Parent", children: [{ name: "Child1", children: [{ name: "Grandchild1", children: [] }, { name: "Grandchild2", children: [] }, { name: "Grandchild3", children: [] }] }, { name: "Child2", children: [] }] };

console.log(findPath([treeFamily], 'Grandchild2'));
console.log(findPath([treeFamily], 'foo'));

Upvotes: 1

Related Questions