Vishnu Shekhawat Vishnu Shekhawat - 2 months ago 8
Javascript Question

What should i do in order to print level also in Breadth first search Algo.

What can be done in the below algo in order to print values level wise in binary tree.

BinarySearchTree.prototype.breadthFirstTraversal = function() {
console.log("Breadth First Traversal");

var q = []
q.push(this.root);//You don't need to write the root here, it will be written in the loop
while (q.length > 0)
{
var n = q.shift();
console.log(n.value); //Only write the value when you dequeue it
if (n.left !=null)
{
q.push(n.left);//enqueue the left child
}
if (n.right !=null)
{
q.push(n.right);//enque the right child
}
}
};

Answer

Store level for each node, and print them only when level changes:

BinarySearchTree.prototype.breadthFirstTraversal = function() {
    console.log("Breadth First Traversal");

    var q = [];
    var prevLevel = -1; // monitor level switch
    var byLevel = []; // store node values for printing
    this.root.level = 0; // set root level
    q.push(this.root);//You don't need to write the root here, it will be written in the loop
    byLevel.push(this.root.value);
    while (q.length > 0)
    {
        var n = q.shift();
        // Next level, print and reset
        if (n.level > prevLevel) {
            console.log(byLevel);
            byLevel = [];
            prevLevel = n.level;
        }
        if (n.left !=null)
        {
            n.left.level = n.level + 1;
            q.push(n.left);//enqueue the left child
            byLevel.push(n.left.value);
        }
        if (n.right !=null)
        {
            n.right.level = n.level + 1;
            q.push(n.right);//enque the right child
            byLevel.push(n.right.value);
        }
    }

    if (byLevel.length > 0) {
        console.log(byLevel);
    }
};
Comments