CODEWITHSUNDEEP
javascripttypescripttree
Code Guru
Code Guru

Reputation: 15578

How to find search path of node in tree js/ts

I have an object that represents a tree.

I want to search node and its search path. To search a node I have created a function that works fine, here is the code

let treeData = {
  id: 1,
  name: "Node 1",
  child: [{
      id: 2,
      name: "Node 2",
      child: [{
          id: 3,
          name: "Node 3"
        },
        {
          id: 4,
          name: "Node 4",
          child: [{
            id: 10,
            name: "Node 10"
          }]
        }
      ]
    },
    {
      id: 5,
      name: "Node 5",
      child: [{
        id: 6,
        name: "Node 6"
      }]
    }
  ]
};


function _searchTree(nodeId, parent) {
  const stack = [parent];
  while (stack.length) {
    const node = stack.pop();
    if (node.id === nodeId) {
      return node;
    }
    if (node.child) {
      stack.push(...node.child);
    }

  }
  return stack.pop() || null;
}
const _node = _searchTree(10, treeData);

console.log("Found node", _node);

This function can find the tree node based on the passed id. But how can I find the search path of the item? The function have provided is stack base, answer with recursion is also acceptable.

Upvotes: 0

Views: 2366

Answers (1)

trincot
trincot

Reputation: 350137

You could push on the stack both the node and the current path and then deal accordingly. I'll assume a path element is an index in the child array.

Here is how that would look:

function _searchTree(nodeId, parent) {
    const stack = [[parent, []]];
    while (stack.length) {
       const [node, path] = stack.pop();
       if (node.id === nodeId) {
          return path;
       }
       if (node.child) {
           stack.push(...node.child.map((node, i) => [node, [...path, i]]));
       }
    }
}

const a = {id: 1,name: "Node 1",child: [{id: 2,name: "Node 2",child: [{id: 3,name: "Node 3"},{id: 4,name: "Node 4",child: [{ id: 10, name: "Node 10" }]}]},{id: 5,name: "Node 5",child: [{id: 6,name: "Node 6"}]}]};
const path = _searchTree(6, a);
console.log(path); // [1, 0]

Note that there are also two corrections to your original code:

  • The final return stack.pop() || null; can just be return null, because stack is empty at that point. If undefined is OK as return value, you can omit the whole line.

  • Before iterating node.child you need to make sure the property exists.

Upvotes: 2

Related Questions