CODEWITHSUNDEEP
javascripttypescriptrecursiontreetreeview
webber
webber

Reputation: 775

How to find a path of a given id?

I have a tree:

type Tree = {
  id: string;
  pathToNode?: string[];
  children: Tree[];
};

export const treeData: Tree = {
  id: '1',
  children: [
    {
      id: '2',
      children: [
        { id: '3', children: [] },
        { id: '4', children: [] },
      ],
    },
    { id: '5', children: [] },
  ],
};

And I wish to find the path to the id and return that path (or in other words, the parent nodes to that node).

This is what I have (but it's not working):

const findPath = (tree: Tree, id: string, pathStack: string[]) => {
  if (tree.id === id) {
    tree.pathToNode = pathStack;
    return { id: tree.id, path: tree.pathToNode };
  }
  pathStack.push(tree.id);

  if (tree.children.length) {
    tree.children.map((node) => findPath(node, id, pathStack));
  }

  return { id: tree.id, path: pathStack };
};

If I call findPath and pass in id: '2', I should get:

const pathStack:string[] = [];

const result = findPath(treeData, '2', pathStack);
// result should equal: {id: '2', pathToNode: ['1']}

If I call findPath and pass in id: '4', I should get:

const pathStack:string[] = [];

const result = findPath(treeData, '4', pathStack);
// result should equal: {id: '4', pathToNode: ['1', '2']}

If I call findPath and pass in id: '5', I should get:

const pathStack:string[] = [];

const result = findPath(treeData, '5', pathStack);
// result should equal: {id: '5', pathToNode: ['1']}

And if I pass in the root id of '1', the response would be {'1', pathToNode: []}

Upvotes: 0

Views: 986

Answers (2)

Sojin Antony
Sojin Antony

Reputation: 2237

Your logic looks fine, only need a few corrections I have added some comments in you code where you need correction

const findPath = (tree: Tree, id: string, pathStack: string[]) => {
  if (tree.id === id) {
    tree.pathToNode = pathStack;  // no need to add pathstack to tree
    return { id: tree.id, path: tree.pathToNode };  // use pathStack instead of tree.pathToNode
  }
  pathStack.push(tree.id);

  if (tree.children.length) {
    tree.children.map((node) => findPath(node, id, pathStack)); // this will loops to all your childs even if you find the result node 
//So use for loop and break the loop when you find the result node 


  }

  return { id: tree.id, path: pathStack };
};

my code is

const findPath = (tree: Tree, id: string, pathStack: string[]) => {
    if (tree.id === id) 
       return { id: tree.id, path: pathStack };

    pathStack.push(tree.id);

    for (const node of tree.children) {
        const result = findPath(node, id, [...pathStack]);
        if (result) return result; //this will stop going deeper or to unwanted childs after getting the result
    }
};

As discussed in the comment to find paths of certain nodes in an array.

let foundPaths = [];
let path
arr.map(element => {
 path = findPath(tree, element.id);
 if(path) {foundPaths.push(path)}
})

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386868

You need to return early for the children and respect the return value.

const
    treeData = { id: '1', children: [{ id: '2', children: [{ id: '3', children: [] }, { id: '4', children: [] }] }, { id: '5', children: [] }] },
    findPath = (tree, id, pathStack = []) => {
        if (tree.id === id) return { id: tree.id, path: pathStack };

        pathStack.push(tree.id);

        for (const node of tree.children) {
            const result = findPath(node, id, [...pathStack]);
            if (result) return result;
        }
    };
    

console.log(findPath(treeData, '4'));
console.log(findPath(treeData, '5'));

Upvotes: 1

Related Questions