1. ## Graphs (algorithm)

Hi,
Let n be a node in a binary, and let l(n) give its left child and r(n) give its right child. I am supposed to write a recursive algorithm MaxBranch(l,r,x), which returns the length of the longest branch of the tree (x is the root of the tree, and length of a branch is the number of arcs on the path from the root to a leaf). I'm not really sure how the psuedocode would look like. If someone could at least give me a hint, I would really appreciate it.

2. Originally Posted by alireza1989
Hi,
Let n be a node in a binary, and let l(n) give its left child and r(n) give its right child. I am supposed to write a recursive algorithm MaxBranch(l,r,x), which returns the length of the longest branch of the tree (x is the root of the tree, and length of a branch is the number of arcs on the path from the root to a leaf). I'm not really sure how the psuedocode would look like. If someone could at least give me a hint, I would really appreciate it.

MaxBranch(l,r,x) = max (MaxBranch(l(l), r(l), l), MaxBranch(l(r), r(r), r) + 1.

That's about as good as I can do, aside from defining MaxBranch to be 0 when neither l(n) nor r(n) exist.

3. Originally Posted by icemanfan
MaxBranch(l,r,x) = max (MaxBranch(l(l), r(l), l), MaxBranch(l(r), r(r), r) + 1.

That's about as good as I can do, aside from defining MaxBranch to be 0 when neither l(n) nor r(n) exist.
I just thought of something else: You want to define MaxBranch(l, r, x) to be MaxBranch (l(l), r(l), l) + 1 when r(x) does not exist but l(x) exists and MaxBranch(l, r, x) to be MaxBranch (l(r), r(r), r) + 1 when l(x) does not exist but r(x) exists. So you have to make 3 initial tests before you can iterate.

4. The algorithm should be something like this:

Code:
public int MaxBranch(node node){
int length = 0;
int lengthMax = 0;
TestChild (node, length, lengthMax);
return lengthMax
}

public int TestChild (node node, int length, int lengthMax){
if (node.l(n) != null){
length = length ++;
TestChild (node.l(n), length, lengthMax);
}
if (length > lengthMax){
lengthMax = length;
}
if (node.r(n) != null){
length = length ++;
TestChild (node.r(n), length, lengthMax);
}
if (length > lengthMax){
lengthMax = length;
}
return lengthMax;
}
Not 100%, but I hope that helps you visualise at least. Basically, you test if there is a left-node, if there is you add one to the length and then test if that node has a left node.....once you get a no, you compare that length to the greatest length so far; then check for right node etc.

It's recursively calling itself within the algorithm.

Hope that helps.