Hemanth.HM

A Computer Polyglot, CLI + WEB ♥'r.

Tree Traversal With ES6 Generator

| Comments

Here is Depth first Tree traversals using ES6 generators, influenced by pep-0255

Currently you must use the --harmony-generators flag when running node 0.11.x to get access to generators.

Depth first traversals:

Pre-order:

  • Visit the root.

  • Traverse the left subtree.

  • Traverse the right subtree.

In-order:

  • Traverse the left subtree.

  • Visit root.

  • Traverse the right subtree.

Post-order:

  • Traverse the left subtree.

  • Traverse the right subtree.

  • Visit the root.

Show me the code!

1
2
3
4
5
6
7

var inorder = function* inorder(node) {
  if (node) {
    yield* inorder(node.left);
    yield node.label;
    yield* inorder(node.right);
  }
}

1
2
3
4
5
6
7

var preorder = function* preorder(node) {
  if (node) {
    yield node.label;
    yield* preorder(node.left);
    yield* preorder(node.right);
  }
}

1
2
3
4
5
6
7

var postorder = function* postorder(node) {
  if (node) {
    yield* postorder(node.left);
    yield* postorder(node.right);
    yield node.label;
  }
}

Let's create a tree:

1
2
3
4
5

function Tree(label, left, right) {
  this.label = label;
  this.left = left;
  this.right = right;
}

1
2
3
4
5
6
7
8

var tree = function tree(list) {
  var n = list.length;
  if (n == 0) {
    return null;
  }
  var i = Math.floor(n / 2);
  return new Tree(list[i], tree(list.slice(0, i)), tree(list.slice(i + 1)));
}

Now if we need to traverse the tree:

1
2
3
4
5
6
7
8
9

var root = tree(['A','B','C','D','E','F','G','H','I']);
var results = [];

for (let value of gntr.preorder(root)) {
    results.push(value);
}

console.log(results);
// Would log  ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']

To make it easier, I created a node moudle gntr hope it helps, happy hacking!

Comments