Javascript Tree Traversal Algorithm

Question

I need help traversing a tree structure in a depth first fashion. I can't come up with an algorithm to do it properly.

My input is this:

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

The output should take 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"
]

This can be done, but it's a bit tricky. Is there any way you can reorganise your data? You're going to have trouble coordinating which of A B C corresponds to which 1 2 and which a b c d; your expected data looks like it follows quite a strange rule. +1 for giving expected data, though. — Bojangles
– Bojangles, Commented Mar 19, 2012 at 0:39
Sure. I can manipulate the input in any way. What form would be preferable? — Adam
– Adam, Commented Mar 19, 2012 at 0:42
The easiest way I can think of is to have a child array instead of a sibling array. This is much easier to traverse as a tree-like structure. — Bojangles
– Bojangles, Commented Mar 19, 2012 at 0:45

0xdw · Accepted Answer · 2017-12-08 06:14:37Z

7

This should do the job:

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);

edited Dec 8, 2017 at 6:14

0xdw

3,8522 gold badges29 silver badges44 bronze badges

answered Mar 19, 2012 at 0:49

icyrock.com

28.7k4 gold badges72 silver badges92 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Community · Accepted Answer · 2017-05-23 12:08:35Z

2

What you're looking for is the cartesian product of a list of lists, it has been asked before. Borrowing from the accepted answer for that 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"]

edited May 23, 2017 at 12:08

CommunityBot

11 silver badge

answered Mar 19, 2012 at 0:46

Óscar López

237k38 gold badges321 silver badges391 bronze badges

7 Comments

ajax333221 Over a year ago

I think you should include the permalink, because in theory they can change the accepted answer and post 100 answers more (and it would be pretty hard to find it then)

Óscar López Over a year ago

@ajax333221 agreed, I added the permalink as you suggested.

Adam Over a year ago

This is more elegant and more generalized, but it doesn't solve the specific problem and there is an error in the current version.

Óscar López Over a year ago

@Adam I just updated my answer, I made the code a little more clear but apart from that, I couldn't find the error you were talking about, what's it?

Adam Over a year ago

SyntaxError: Unexpected token for

|

Collectives™ on Stack Overflow

Javascript Tree Traversal Algorithm

2 Answers 2

Comments

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related