# Software engineering notes

## children of the node

Suppose you’d like to traverse through a family tree in JavaScript, printing each generation of children on a single line. Why? Who knows, but lets suppose you’re so possessed by the idea that you’re losing sleep over it.

The tree looks like this:

```             0

|

1       -       2

|                 |

3    -    4            -    6```

The correct output would look like this:

0

1 2

3 4 6

This sounds a lot like a breadth-first search to me, but let’s forget for a moment that Wikipedia exists and think through this.

A verbal walk-through of the problem might sound like this:

1. Visit root node
2. Print root node and <br> tag
3. Print all the children of the root node and another <br> tag
4. Print all the children of each child node and another <br> tag …

Ok, that’s a mess.  Seems like recursion might help simplify things, but then I’d end up with a stack-based traversal due to the call stack, an idea I find amazing.  But what I want is something more like a queue; first in, first out; root in, root out, children in children out, children’s children in, children’s children out … breath in, breath out.  I feel like I’m in yoga class.  So soothing.  Here’s a Buddha by a koi pond:

Verbal walk through part deux:

1. Enqueue root node
2. Dequeue node, print, and enqueue each child of the node
3. Repeat from step 2

Supposing we have a queue, Q.  We can depict the tree, T, in code like this:

```var T = [
{ left: 1, right: 2 },
{ left: 3, right: 4 },
{ left: null, right: 6 },
{ left: null, right: null },
{ left: null, right: null },
{ left: null, right: null },
{ left: null, right: null }
];
```

Following the second approach, we’d get

1. Q = [node 0]
2. “node 0”, Q = [node 1, node 2]
3. “node 1”, Q = [node 2, node 3, node 4]
4. “node 2”, Q = [node 3, node 4, node 6]
5. “node 3”, Q = [node 4, node 6]
6. “node 4”, Q = [node 6]
7. “node 6”

which would be correct, but the line breaks are off.  We need to print all the children of a generation before printing a line break.

Verbal walk through take three:

1. Enqueue root node
2. While there are nodes in the queue, dequeue node, print node, and enqueue children of the node
3. Print a line break
4. Repeat from step 2

Following the third approach, we’d get

1. Q = [node 0]
2. “node 0”, Q = [node 1, node 2]
3. “node 1 node 2”, Q = [node 3, node 4, node 6]
4. “node 3, node 4, node 6”, Q = []

That’s it!  Nice.  Here’s some code:

```function printTree(tree){

var queue = [];

// enqueue root
queue.push( 0 );

do {

var len = queue.length;

// for each node in the queue
for( var i = 0; i < len; i++ ){

// dequeue
var index = queue.shift();

// print node
document.writeln( index );

var node = tree[ index ];

// enqueue children of the node
if( node.left ) {
queue.push( node.left );
}
if( node.right ) {
queue.push( node.right );
}

}

// print a line break
document.writeln("<br>");

// repeat
} while( 0 !== queue.length );

}

// run it
printTree(T);
```

Written by Erik

January 18, 2011 at 11:22 pm