Find lowest common ancestor of tree like object (not binary tree) using recursion js-CodePudding

I need some help with finding Lca of two nodes in the tree. So can anybody explain how to use recursion to traverse to some point and get result back. I saw many examples but no one of them can realy help me. This sort of problem is really new to me, I'm never used recursion for traverse the tree structures. Apreciate any help!

This is how my tree looks like, and this is one of many examples because it's randomly generated, and also I can't use any loops or forEach, array methods are allow only.

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]};

This is what I'm trying to do:

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

const max = graph => {
    return Math.max(...graph.values, ...graph.children.map(graphNode => max(graphNode)));  
};

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

    const findPath = (graph, key1, key2) => {
        if (graph.values.includes(key1) || graph.values.includes(key2)) {
            return graph.values;
        };
        
        const arr = [graph.values].concat(graph.children.map(graphNode => {
            return findPath(graphNode, key1, key2);
        }));
    
        return arr;
    };

    const Lca = findPath(graph, minValue, maxValue);
    return Lca;
}

CodePudding user response：

Your findPath function returns graph.values as the base case, which is not going to help to build a path. Instead the indexes of the children.map iteration should be collected as the path.

And then when you have both the path to the minimum and the path to the maximum, you should ignore the prefix they have in common and count the remaining parts which represent the edges on the path between the two extreme nodes.

Here is a possible implementation:

// the selector argument is a function that here will be either Math.min or Math.max:
function findPath(tree, selector) {
    const bestOf = (a, b) => selector(a[0], b[0]) === a[0] ? a : b;  
    const recur = (node, path) =>
        node.children.reduce((acc, child, i) => 
            bestOf(acc, recur(child, path.concat(i))),
        [selector(...node.values), path]);
    return recur(tree, [])[1];
}

function distanceMinMax(tree) {
    const min = findPath(tree, Math.min),
          max = findPath(tree, Math.max),
          common = min.findIndex((child, depth) => max[depth] != child);
    return min.length   max.length - (common < 0 ? min.length : common) * 2;
}

// Demo tree: the minimum is 1 and maximum is 10. Distance is 3.
const tree = {
    children: [{ 
        children: [{ 
            children: [],
            values: [3]
        }],
        values: [5, 1]
    }, {
        children: [{
            children: [{
                children: [],
                values: [9]
            }],
            values: [10]
        }],
        values: [8, 6]
    }],
    values: [2, 4, 7]
};

console.log(distanceMinMax(tree)); // 3

Remarks

You wrote that you ... "can't use any loops or forEach, array methods are allowed only."

This is really a contradiction because:

.forEach() is an array method;
your code uses .map() which is quite similar to .forEach();
both .map() and .includes() represent a loop;
It is quite natural to use loops when your data structure has children arrays, as any solution will have to visit each entry of such an array.