Print all paths to leafs of a tree-like list array and concatenate corresponding values in the path with special conditions

Question

I have an array consisting of keys and values where keys are a tree like numbered list. This is the input array:

inputArr =  [
             ["1", "p"], 
             ["1.1", "q"], 
             ["1.2", "a"], 
             ["1.2", "b"], 
             ["1.2", "c"], 
             ["1.2.1", "d"], 
             ["1.2.2", "4"], 
             ["1.2.2.1", "5"], 
             ["1.3", "6"], 
             ["1.4x", "7"], 
             ["2", "8"], 
             ["2.1", "9"], 
             ["2.2", "10"], 
             ["2.2.1x", "11"],
             ["2.2.2", "12"],
             ["3", "13"], 
             ["4", "14"]
            ];

Expected output:

outputArr = [
             ["1.1", "p,q"], 
             ["1.2.1", "p,a,b,c,d"], 
             ["1.2.2.1", "p,a,b,c,4,5"], 
             ["1.3", "p,6"], 
             ["1.4x", "7"], // not "p,7", because key has a tailing 'x' 
             ["2.1", "8,9"], 
             ["2.2.1x", "11"], //not "8,10,11", because key has a tailing 'x'
             ["2.2.2", "8,10,12"],
             ["3", "13"], 
             ["4", "14"]
            ];

---

Let me explain the first output: ["1.1", "p,q"] :

It is the first leaf. It's path is: "1"->"1.1". The values in the path are: "p" , "q".

---

Let me explain the second output: ["1.2.1", "p,a,b,c,d"] :

It is the second leaf. Here, I have treated duplicate keys as extension of one.["1.2", "a"],["1.2", "b"],["1.2", "c"] means ["1.2", "abc"] .

So, the path of the second leaf is : "1"->("1.2" + "1.2" + "1.2")->"1.2.1".

---

Let me explain the fifth output:["1.4x", "7"] :

Please note: it is not "p,7". Since the key has a tailing 'x', this leaf should not take 'p' in the output.

Same logic is applicable for seventh output.

---

What I have done so far:

Here is my attempts to this issue so far.

This is a piece of code I am using right now:

//////////////////////////////////////

function getTreeBranch(arr, c, p) {

    var outputArr = [],
    s = [],
    curr,
    next;

    for (var i = 0; i < arr.length - 1; i++) {
        curr = arr[i];
        next = arr[i + 1];
        currLevel = curr[c].split(".").length
        nextLevel = next[c].split(".").length

            if (currLevel == 1) {
                s = []
                s.push(curr[p]);
                if (currLevel == nextLevel)
                    outputArr.push([curr[c], s.join(',')]);
            } else if (currLevel < nextLevel) {
                s.push(curr[p]);
            } else if (currLevel == nextLevel) {
                s.push(curr[p]);
                outputArr.push([curr[c], s.join(',')]);
                s.pop();
            } else if (currLevel > nextLevel) {
                outputArr.push([curr[c], s.join(',') + ',' +curr[p]]);
                for (j = 0; j < (currLevel - nextLevel); j++) {
                    s.pop()
                }
            }
    }

    var lastItem = arr[arr.length - 1];
    if ((lastItem[c].length) == 1) {
        s = []
    }
    s.push(lastItem[p]);
    outputArr.push([lastItem[c], s.join(',')]);

    return outputArr

}

But this function can't handle duplicate keys and tailing 'x's.

---

Can you suggest any correction or update, any alternative piece of code, any algorithm or hint about the problem? Any help will be much appreciated.

Answer 1

Filter the leaves by checking that there are no other entries which have them as the parent, making a special case for the entries with an 'x'.

Then, assuming the inputArr is in the correct order, find all parents and include them (again, with a special case where there is the 'x').

const inputArr = [["1","p"],["1.1","q"],["1.2","a"],["1.2","b"],["1.2","c"],["1.2.1","d"],["1.2.2","4"],["1.2.2.1","5"],["1.3","6"],["1.4x", "7"],["1.4x", "s"],["1.4x", "g"],["2","8"],["2.1","9"],["2.2","10"],["2.2.1x","11"],["2.2.2","12"],["3","13"],["4","14"]]

const outputArr = [...new Set(inputArr.map(([k])=>k))]
  .map(k=>[k,inputArr.filter(([i])=>i===k).map(([k,v])=>v)]).filter(([a])=>
    a.endsWith('x') || !inputArr.some(([b])=>b!==a && b.startsWith(a)
)).map((([a,b])=>[a,(a.endsWith('x')?b:
  inputArr.filter(([c])=>a.startsWith(c)).map(([c,d])=>d)).join(',')
]))

console.log(outputArr)