#search techniques

Find a node in skip graph with a given key

Void findOne(Node n, int searchOp, node startNode, int searchKey, int level) 

{ 

If (n.key == searchKey) then 

    Inform n to start_node 

If n.key < searchKey then 

    While level >= 0 do 

      If (nRlevel).key < searchKey then 

          Recursively call at nRlevel 

           Break; 

      Else level = level –1 

Else 

      While level >= 0 do 

       If (nLlevel).key  > searchKey then 

           Recursively call at nLlevel 

           Break; 

       Else level = level –1 

If (level < 0) then 

   Inform n to startNode  

} 

Void findallInrange(ref List<Node> result, int min, int max) 

{ 

// all the nodes at the lowest level between min and max are the candidates 

FindOne say at min 

Then binary chop between min and max at lowest level. 

}

#codingexercise

Find the distance between two nodes in a binary tree

distance = distance from root for first + distance from root for second - 2 * distance from root for LCA
Node getLCAAndDistance(Node root, int n1, int n2, int level, ref int d1, ref int d2, ref int dist)
{
if (root == null) return null;
if (root.key == n1){
d1 = level;
return root;
}
if (root.key == n2){
d2 = level;
return root;
}
var llca = getLCAAndDistance(root.left, n1, n2, level+1, ref d1, ref d2, ref dist);
var rlca = getLCAAndDistance(root.right, n1, n2, level+1, ref d1, ref d2, ref dist);
if (llca && rlca)
{
dist = d1+d2-2*level;
return root;
}

if (llca != null)

   return llca;

else

   return rlca;

}
Node getDistance(Node root, int n1, int n2)
{
int d1 = -1;
int d2 = -1;
int dist = -1;
var lca = getLCAAndDistance(root, n1, n2, 1, ref d1, ref d2, ref dist);
if (d1 == -1 && d2 == -1) return dist;
if (d1 == -1) {dist = findlevel(lca, n2, 0); return dist;}
if (d2 == -1) {dist = findlevel(lca, n1, 0); return dist;}
return -1;
}