1
\$\begingroup\$

I am new to Trees and BFS/DFS as well as programming and I decided to play around to learn how to traverse trees.

I did not want to use the shift() JavaScript function.

The constructors and code are below. Since I am new, I would like to know how I may improve my code. If the method implemented is inefficient, and if so, how may I make it more efficient.

I realize I could possibly combine the traverse() and secondTrav() function in to one, by including some conditionals, so I will be trying to fix this as well.

Node constructor:

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

Tree constructor:

function Tree(){
      this.root = null;
}

Pushes Nodes in to Tree (Binary):

Tree.prototype.push = function(val){

     var root = this.root;

     if(root === null){
       this.root = new Node(val);
       return;
     }

     var currentNode = root;
     var newNode = new Node(val);


     while(currentNode !== null){
       if(val < currentNode.data){
         if(currentNode.left === null){
           currentNode.left = newNode;
           break;
         }else{
           currentNode = currentNode.left;

         }
       }else{
         if(currentNode.right === null){
           currentNode.right = newNode;
           break;
         }else{
           currentNode = currentNode.right; 
         }
       }
     }
   }

Function to implement BFS, returns Node values as an Array:

Can traverse() and secondTrav() be combined?

function bfs(tr){

    var stackLeft=[];
    var stackRight=[];
    var order = [];
    var currentNode1 = tr.root;

    stackLeft.push(currentNode1);
    traverse(stackLeft);


    function traverse(stackLeft){
      stackRight=[];
      for(i=0; i<=stackLeft.length-1; i++){
        order.push(stackLeft[i].data)

        if(stackLeft[i].left !== null){
          stackRight.push(stackLeft[i].left);
        }
        if(stackLeft[i].right !== null){
          stackRight.push(stackLeft[i].right);
        }
      }
      if(stackRight.length === 0 && stackLeft.length === 0){
        return order
      }else{
      secondTrav(stackRight);
      }
    }

    function secondTrav(stackRight){
      stackLeft=[];
      for(i=0; i<=stackRight.length-1; i++){
        order.push(stackRight[i].data)
        if(stackRight[i].left !== null){
          stackLeft.push(stackRight[i].left);
        }
        if(stackRight[i].right !== null){
      stackLeft.push(stackRight[i].right);
        }
      }
      traverse(stackLeft);
    }
    console.log(order);
}

The above code works for the following implementation:

var newTree = new Tree();

newTree.push(100);
newTree.push(90);
newTree.push(110);
newTree.push(105);
newTree.push(95);
newTree.push(92);
newTree.push(97);
newTree.push(107);
newTree.push(102);

bfs(newTree);
\$\endgroup\$
  • \$\begingroup\$ (Welcome to CR!) If it is a search: what is it expected to find? I prefer traversals with no "early out"/nothing to find, well, traversal. You have description all around your code - how about putting some in? Since I am new, I would like to know how I may improve if lucky, you keep like that (inquisitive - new does wear off). \$\endgroup\$ – greybeard Dec 30 '17 at 23:34
  • \$\begingroup\$ combine the traverse() and secondTrav() function for a first step, put into words what each does, pinpointing differences. \$\endgroup\$ – greybeard Dec 30 '17 at 23:39
  • \$\begingroup\$ Hi greybeard! Thanks for the suggestions! I will try to edit later and add some comments within code \$\endgroup\$ – PradeepLR Dec 31 '17 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.