Erik's blog

Code, notes, recipes, general musings

children of the node

leave a comment »

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:

"goldie the fish is blessed by the garden buddha"

golden buddha by Paul Moody

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

Written by Erik

January 18, 2011 at 11:22 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: