I'm trying to find min and max values in tree like object using recursion, but I don't actualy understand how to find this values. Also my function must be pure and I can't use loops or forEach. Only map, reduce, filter are avalaible. So this is how my data looks like:

const tree = {
children: [ 
    { 
        children: [
            { 
                children: [],
                values: [15.667786122807836]
            }
        ],
        values: [35.77483035532576, 1.056418140526505]
    },
    {
        children: [
            {
                children: [
                    {
                        children: [],
                        values: [67.83058067285563]
                    }
                ],
                values: [98.89823527559626]
            }
        ],
        values: [51.49890385802418, 41.85766285823911]
    },
],
values: [6.852857017193847, 28.110428400306265, 51.385186145220494]};

I'm trying to do something like this:

const min = graph => {
if (!graph.children.length && !graph.values.length) return;

if (!graph.children.length && graph.values.length) {
    return Math.min(...graph.values);
}

return graph.children.map(el => {
    const minValue = Math.min(...el.values);
    min(el);
    return minValue;
});

};

But this not work well. So guys can anybody explain how the callstack works, maybe give me some good examples, and explain how to solve my problem. Thanks for the help and sorry for the bad English). Oh, and also)) how to get the distance between two nodes in the different depth level?

CodePudding user response：

I'm not a JS programmer but am always looking to practice. Here's what I came up with:

const tree = {
  children: [{
      children: [{
        children: [],
        values: [15.667786122807836]
      }],
      values: [35.77483035532576, 1.056418140526505]
    },
    {
      children: [{
        children: [{
          children: [],
          values: [67.83058067285563]
        }],
        values: [98.89823527559626]
      }],
      values: [51.49890385802418, 41.85766285823911]
    },
  ],
  values: [6.852857017193847, 28.110428400306265, 51.385186145220494]
};

function treeMin(graph) {
  if (graph.children.length == 0) return Math.min(...graph.values);
  return Math.min(...graph.values,
                  graph.children.reduce((prev, cur) =>
                     Math.min(prev, treeMin(cur)), Number.MAX_SAFE_INTEGER
                  ));
}

console.log(treeMin(tree));

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

I gave the function a name to make the recursive calls. The first thing it does is check if there are no children. If not, it just returns the min of the values.

If there are children, return the min of values and the result of calling reduce on the children. Inside reduce, the recursive calls are made.

Note: it does not handle the case where values is empty. This can be easily added.

CodePudding user response：

Usually with homework questions, I would prompt for more dialog with the OP, but as this already has a working, accepted answer, I'll just add a simpler one:

const min = ({values = [], children = []}) => 
  Math .min (...values, ... children .map (min))

const tree = {children: [{children: [{children: [], values: [15.667786122807836]}], values: [35.77483035532576, 1.056418140526505]}, {children: [{children: [{children: [], values: [67.83058067285563]}], values: [98.89823527559626]}], values: [51.49890385802418, 41.85766285823911]}, ], values: [6.852857017193847, 28.110428400306265, 51.385186145220494]};

console .log (min (tree))

<iframe name="sif2" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

We just use Math.min, spreading the current values and the results of recursive calls to each of its children into arguments to it. We default both values and children to empty arrays in case either is missing at any node.

Clearly max is a trivial change to this.