var insert = function(value, parent) {

  var node = { val: value, children: [] };

​

  if (parent) {

    // Add a child to the parent.

    parent.children.push(node);

  }

  return node;

}

​

var traverseDFS = function(node, callback) {

  if (callback) {

    callback(node);

  }

​

  for (var i=0; i<node.children.length; i++) {

    traverseDFS(node.children[i], callback);

  }

}

​

var traverseBFS = function(node, callback) {

  var fringe = [ node ];

​

  while (fringe.length) {

    node = fringe.pop();

​

    if (callback) {

      callback(node);

    }

    // Collect all nodes on the fringe.

    for (var i=0; i<node.children.length; i++) {

      fringe.splice(0, 0, node.children[i]);

    }

  }

}

​

var traverseA = function(node, cost) {

  var depth = 0;

  var fringe = [ { node: node, h: cost(node), g: depth } ];

  var solution = [];

  while (fringe.length) {

    // Explore the next state with the lowest cost.

    var current = fringe.pop();

    console.log('Checking ' + current.node.val);

    if (current.h === 0) {

      // Solution found! Walk backwards from leaf back to parent.

      solution = [];

      while (current) {

        // Add this node to the front of the array.

        solution.unshift(current.node);

        current = current.parent;

      }

      break;

    }

    // Collect all nodes on the fringe.

    for (var i=0; i<current.node.children.length; i++) {

      var child = current.node.children[i];

      fringe.push({ parent: current, node: child, h: cost(child), g: current.g + 1 });

    }

    // Sort the nodes by their heuristic score in descending order (we pop() from the end, so we want the lowest score there).

    fringe = fringe.sort(function(a, b) { return (b.h + b.g) - (a.h + a.g); });

  }

  return solution;

};

​

var toArray = function(head) {

  var result = [];

  traverseDFS(head, function(node) {

    result.push(node.val);

  });

  return result;

}

​

var root = insert('red');

var r1 = insert('red', root);

insert('orange', r1);

insert('purple', r1);

insert('brown', r1);

​

var g1 = insert('green', root);

insert('yellow', g1);

insert('white', g1);

insert('violet', g1);

​

var b1 = insert('blue', root);

var p1 = insert('pink', b1);

insert('teal', p1);

insert('magenta', p1);

insert('tan', p1);

var g2 = insert('gray', b1);

insert('mauve', g2);

insert('lime', g2);

​

​

var solution = traverseA(root, function(node) {

  var cost = 100;

  if (node.val === 'red') {

    cost = 75;

  }

  else if (node.val === 'blue') {

    cost = 50;

  }

  else if (node.val === 'gray') {

    cost = 25;

  }

  else if (node.val === 'lime') {

    cost = 0;

  }

​

  return cost;

});

​

for (var i=0; i<solution.length; i++) {

  console.log(solution[i].val);

}