CODEWITHSUNDEEP
javascriptbinary-search-tree
Lkoprivica
Lkoprivica

Reputation: 39

Given a Binary Search Tree and two nodes, n1 and n2, write a function that finds the distance between the two nodes

Given a Binary Search tree I need to write a function that finds the distance between 2 nodes. I think I am close with this one but it does not seem to work properly. If I want to search the distance between nodes that are on the same side of the tree. Not sure how to fix this. Any tips would be greatly appreciated. Below is the code I have so far. My code is in Javascript.

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

function BinarySearchTree(value) { 
 this.root = null;
};

BinarySearchTree.prototype.push = function(val){
   var root = this.root;

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

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

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

}

BinarySearchTree.prototype.levelOfNode = 
    function(root, key, level){
      if(root === null){
        return -1;
      }else if(root.value === key){
        return level;
      }
  let l = this.levelOfNode(root.left, key, level+1)
    if (l!== -1){
      return l;
    }
    return this.levelOfNode(root.right, key, level +1)
  }

BinarySearchTree.prototype.lca = function(root, n1, n2){
   if(!root) return;
   var val = root.value;
   if(n1<val && n2<val){
     return lca(root.left, n1, n2);
   }
   if(n1>val && n2>val){
     return lca(root.right, n1, n2);
  }
  return this.root;
}

BinarySearchTree.prototype.findDistance = function(root, n1, n2){
  let lcaValue = this.lca(root, n1, n2);

  let l1 = this.levelOfNode(lcaValue, n1, 0);
  let l2 = this.levelOfNode(lcaValue, n2, 0);

  return l1 + l2;

}

let tree = new BinarySearchTree();

tree.push(4);
tree.push(8);
tree.push(9);
tree.push(11);
tree.push(3);

tree.findDistance(4,8,11);

Upvotes: 1

Views: 241

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386680

While you have a tree which looks like 

   4
3     8
         9
           11

You could get the path from root for every target and

[4, 8]
[4, 8, 9, 11]

eliminate all common nodes. Then check if one path array is empty and take the length of the other one.

If you got two not empty arrays, you could add the length of both, like

[4, 3]
[4, 8, 9]

after eliminating of common nodes

[3]
[8, 9]

Then add both lengths

1 + 2 = 3

Upvotes: 2

Related Questions