Breadth First Traversal

by russau

JavaScript

function Node (data) {
    this.left = null;
    this.right = null;
    this.data = data;
}

var a = new Node('A');
var b = new Node('B');
var c = new Node('C');
var d = new Node('D');
var e = new Node('E');


a.left = b;
a.right = c;
c.left = d;
d.right = e;

var serialized  = breadthSerialize(a);
$('body').append(serialized);
$('body').append('<br>');
var newTree = deserialize(serialized);

var newSerialized = breadthSerialize(newTree);
$('body').append(newSerialized);
$('body').append('<br>');

function breadthSerialize(root)
{
    var q = [];
    q.push(root);
    var serial = [];
    
    while (q.length > 0)
    {    
        // http://stackoverflow.com/questions/1590247/how-do-you-implement-a-stack-and-a-queue-in-javascript
        var node = q.shift();
        if (node != null) {
            serial.push(node.data);
            q.push(node.left);
            q.push(node.right);
        }  
        else
        {
            serial.push('null');
        }
    }
    return serial.join(',');
}

function deserialize(blob)
{

    var q = [];
    var arr = blob.split(',');
    
    var root =  new Node(arr.shift());
    q.push(root)
    
    while (arr.length > 0)
    {   
        var parent = q.shift();
        var left = arr.shift();
        var right = arr.shift();
        if (left != "null") {
            parent.left = new Node(left);
            q.push(parent.left);
        }
        if (right != "null") {
            parent.right = new Node(right);
            q.push(parent.right);
        }
    }
    return root;
}