Javascript Tree Traversal Algorithm

Question

I need help that crosses the tree structure first. I can't think of an algorithm to do it right.

My input is as follows:

[ ["A", "B", "C"], ["1", "2"], ["a", "b", "c", "d"] ] 

The output should be of the form:

 [ "A/1/a", "A/1/b", "A/1/c", "A/1/d", "A/2/a", "A/2/b", "A/2/c", "A/2/d", "B/1/a", "B/1/b", "B/1/c", "B/1/d", "B/2/a", "B/2/b", "B/2/c", "B/2/d", "C/1/a", "C/1/b", "C/1/c", "C/1/d", "C/2/a", "C/2/b", "C/2/c", "C/2/d" ] 

Answer 1

This should complete the task:

 function traverse(arr) { var first = arr[0]; var ret = []; if (arr.length == 1) { for (var i = 0; i < first.length; i++) { ret.push(first[i]); } } else { for (var i = 0; i < first.length; i++) { var inn = traverse(arr.slice(1)); for (var j = 0; j < inn.length; j++) { ret.push(first[i] + '/' + inn[j]); } } } return ret; } var inp = [ ["A", "B", "C"], ["1", "2"], ["a", "b", "c", "d"] ]; var out = traverse(inp); console.log(out); 

Answer 2

What you are looking for is the Cartesian product of a list of lists previously asked . Borrowing from the accepted answer to this question, you can do this in Javascript 1.7:

 function product() { return Array.prototype.reduce.call(arguments, function(as, bs) { return [a.concat(b) for each (a in as) for each (b in bs)]; }, [[]]); }; function convert(lst) { var solution = []; for (var i = 0; i < lst.length; i++) { solution.push(lst[i][0] + "/" + lst[i][1] + "/" + lst[i][2]); } return solution; }; convert(product(["A", "B", "C"], ["1", "2"], ["a", "b", "c", "d"])); > ["A/1/a", "A/1/b", "A/1/c", "A/1/d", "A/2/a", "A/2/b", "A/2/c", "A/2/d", "B/1/a", "B/1/b", "B/1/c", "B/1/d", "B/2/a", "B/2/b", "B/2/c", "B/2/d", "C/1/a", "C/1/b", "C/1/c", "C/1/d", "C/2/a", "C/2/b", "C/2/c", "C/2/d"]