How to get A Path from a nested object tree-CodePudding

I am currently stuck with a problem that when I started out seemed not too hard to solve for me, but I am stuck for a couple of hours now, so here we go:

Given this nested objects/tree:

const tree = {
    value: 50, children: [
        {
            value: 17, children: [
                {
                    value: 12, children:
                        [
                            { value: 9, children: null },
                            { value: 14, children: null }
                        ]
                },
                { value: 23, children: null }
            ]
        }, {
            value: 72, children: [
                {
                    value: 54, children: [
                        {
                            value: 67, children: null
                        }
                    ]
                },
                {
                    value: 76, children: null
                }
            ]
        }
    ],
}

I am trying to find a function that gives me the path to a value

function findPath(tree, target){
...
}

and the function will return something like

findPath(tree, 67);
<==============>
[50, 72, 54, 67]

I'm new to code. I hope I'll get you help to solve this. Thanks.

CodePudding user response：

One option with trees is recursion. Recursively search children until the value is found. On the way back up, build the array. Not sure this is the most efficient but it works.

const tree = {
  value: 50,
  children: [{
    value: 17,
    children: [{
        value: 12,
        children: [{
            value: 9,
            children: null
          },
          {
            value: 14,
            children: null
          }
        ]
      },
      {
        value: 23,
        children: null
      }
    ]
  }, {
    value: 72,
    children: [{
        value: 54,
        children: [{
          value: 67,
          children: null
        }]
      },
      {
        value: 76,
        children: null
      }
    ]
  }],
};

function findPath(tree, target) {
  // The value of this node
  let currentValue = tree.value;
  if (currentValue == target) return [target];
  for (let t of Object.entries(tree)) {
    // Search children
    if (t[0] == "children" && t[1]) {
      for (let child of t[1]) {
        let found = findPath(child, target);
        if (found) {
          return [currentValue].concat(found);
        }
      }
    }
  }
  // Not found in this branch
  return null;
}

console.log(findPath(tree, 67));

CodePudding user response：

You can use recursion to find the path (see comments in code):

function findPath({ value, children }, target) {  
  if(value === target) return [value] // if the value is found return it wrap in an array
  
  for(const child of children ?? []) { // iterate the children or an empty array
    const leaf = findPath(child, target) // use findPath on all children
    
    if(leaf) return [value, ...leaf] // if a leaf is found (not null) spread it to the current array, and return it
  }
  
  return null
}

const tree = {"value":50,"children":[{"value":17,"children":[{"value":12,"children":[{"value":9,"children":null},{"value":14,"children":null}]},{"value":23,"children":null}]},{"value":72,"children":[{"value":54,"children":[{"value":67,"children":null}]},{"value":76,"children":null}]}]}

const result = findPath(tree, 67)

console.log(result)