CODEWITHSUNDEEP
jsontypescripthierarchical-data
Mark
Mark

Reputation: 4950

Hierarchical JSON - find complete path to an object

I have a large JSON object that serves a purpose of the tree source. within this JSON I need to find an object with a given ID and build the complete to it meaning collecting its parents. To illustrate it's like in the file system: folde1/folder2/folder3/file.txt. Here is my recursive function to find the object:

private find(source, id): string[] {
    for (const key in source)
    {
        var item = source[key];
        if (item.id === id) {
            return this.indexes;
        }                
        
        if (item.children) {
            this.indexes.push(key);
            var subresult = this.find(item.children, id);
            if (subresult) {
                this.indexes.push(key);
                return this.indexes;
            }                    
        }
    }
    return null;
}

My problem is that while looking for the object I am picking up a lot of false parents thus the result has extra data.

Any idea how make it work? I am also thinking to start looking for the path from the inside, but dont know how to get a parent of the found object.

Thanks for the help.

Upvotes: 0

Views: 1328

Answers (1)

jcalz
jcalz

Reputation: 328398

I'm going to make a general answer and hopefully it applies to your actual structure. I assume a Tree looks like this:

interface Tree {
  id: string;
  children?: Record<string, Tree>;
}

Each Tree has an id, and an optional children property which is a dictionary of Trees. A possible implementation of findPathById() follows:

function findPathById(tree: Tree, id: string, curPath: string[] = []): string[] | undefined {
  if (tree.id === id) return curPath;
  const children = tree.children ?? {}
  for (let k in children) {
    const possibleAnswer = findPathById(children[k], id, [...curPath, k]);
    if (possibleAnswer) return possibleAnswer;
  }
  return undefined;
}

The approach here is that the function takes a parameter curPath corresponding to the path to the current tree node, to which subsequent path entries can be appended. If this path is left out, then it will be assumed to be empty. If the tree passed in has the desired id, then we've found it and can return curPath. Otherwise, we start checking each property of children (if it exists) to see if the id exists in one of the children, calling findPathId on the child value, with a new curPath made by appending the child key to the current path. If we get a result, we return it. Otherwise, we go on to the next child. If we haven't found the id after checking the current item and recursively down through its children, then it isn't in there, and we return undefined.

Here's a test:

const tree: Tree = {
  id: "A",
  children: {
    x: {
      id: "B", children: {
        t: { id: "E" },
        u: { id: "F" }
      }
    },
    y: {
      id: "C", children: {
        v: { id: "G" },
        w: { id: "H" }
      }
    },
    z: { id: "D" }
  }
}

console.log(findPathById(tree, "A")); // []
console.log(findPathById(tree, "D")); // ["z"]
console.log(findPathById(tree, "G")); // ["y", "v"]
console.log(findPathById(tree, "J")); // undefined

This looks like the behavior we want. The "A" id is found at the root, so the path is an empty array. The "D" id is found at tree.children.z, so the path is ["z"]. The "G" id is found at tree.children.y.children.v, so the path is ["y", "v"]. And finally, the "J" id is never found, so the path is undefined.

Playground link to code

Upvotes: 1

Related Questions