algorithm to find distance between two nodes in a tree
Hi
I am trying to implement an algorithm to find the distance between any two nodes in a tree .. The following pseudo-code is what I have so far.. Anyone knows of a better way to do this , please help ..
Assume we have a pointer to the given nodes n1 and n2 .
step1) start with n1 and recursively perform depth first search (ie check if n2 is anywhere in the subtree with n1 as a root)
step2) as each node is traversed , mark it as visited - after all children are visited , mark the parent as visited..
step 3) if node n2 is still not found , go to n1's parent and search other siblings except the ones already visited.
I am not even sure if this is the correct way to do this.. Here is the recursive function I wrote..
void dist_calc(Treenode t1, Treenode t2, int d) {
//check if any of t1's children equals t2
for (int k = 0; k < t1.children.size(); k++) {
String v = ((Treenode) t1.children.get(k)).value;
v = v.trim();
String x = t2.value.trim();
if (x.equals(v)) {
d += 1;
System.out.println("distance is " + d);
System.out.println("curr child is " + v);
System.out.println("curr parent is " + t1.value);
found = true;
break;
}
}
if (found)
return;
else {
//not found in children .. recursively search each subtree
if (t1.children.size() > 0) {
d += 1;
for (int q = 0; q < t1.children.size(); q++) {
Treenode t = (Treenode) t1.children.get(q);
if (!t.visited) {
dist_calc(t, t2, d);
}
}
t1.visited = true;
}
else
t1.visited = true;
}
//if not found .. go up one level and repeat..
if (!found) {
//d-=1;
if (t1.parent != null) {
d = 1;
if (t1.parent.value.equals(t2.value)) {
System.out.println("distance is " + d);
found = true;
} else {
if (!found) {
Treenode p = t1.parent;
dist_calc(p, t2, d);
}
}
} else {
System.out.println("distance is infinity ");
}
}
}
I am getting a stack overflow exception , which means there is some logical error.. If theres a better algorithm for this , please do let me know .. thanks
