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