Binary Tree help needed

[trilobyte]

I know how to find the longest root-to-leaf path in the tree, however I don't know how to find a tree's shortest-root-to-leaf path.

I'm having problems plugging down the recursive algorithm for this. I have a feeling my upcomming exam will have something like this, so any quick help in figuring this out would be great.

 

[Bloodstein]

Hmn....ok, i don't know of any algorithms to solve ur problem with binary trees. However, a reasonably efficient algortim exists for graphs (djikstra's algorithm) that works out the shortest path between two nodes in a graph.

You should be able to apply djikstra's algorithm on your binary tree (or any tree) as trees are a special type of graph. Just use the root node as the starting node
Of course, since this is an algorithm based on graphs, you gotta identify which nodes in ur tree are leaf nodes to determine the shortest root-to-leaf path.

http://www.cs.auckland.ac.nz/compsci220sc/lectures/ute-files/lect9.pdf's a bit more on the algorithm
And http://www.cs.auckland.ac.nz/compsci220sc/lectures/GraphDW/GraphDW.html's an applet of the algorithm

If u're not too worried 'bout efficiency, you could try Floyd's algorithm http://www.cs.auckland.ac.nz/compsci220sc/lectures/ute-files/lect10.pdf. It is simpler than Djikstra's algorithm but not too efficient...

Btw, could you describe ur algorithm to find the longest root-to-leaf path in a tree? Maybe a slight modification of the algorithmn could solve ur problem....

 

[trilobyte]

I can't figure out how those algos apply to my tree :/

normally I'd do this to find the longest root-to-leaf path:

int long(nodePtr ptr)
{
if(ptr == NULL)
return 0;
else
{
return 1+ max(long(ptr->left), long(ptr->right));
}
}

where max returns the biggest of the 2 parameters

Now, for me, logic says to just make a min(int x, int y) and use that in place of max to find the smallest root-to-leaf path. However it doesn't seem to work correctly (it'll always give me a 2 for the shortest root-to-leaf path).

 

[ant80]

Well, I remember doing it in Ohio state. Unlike the longest path, you have to check each one separately. That is the only way, imho. Check this sample pseudocode out.


minimum_path(num = cost until now)

if (this is last root)
return num+1 (or 0) depending on what u want
else
{
call (minimum_path_left) with num+1
call (minimum_path_right) with num+1

return num+minimum(right,left)
}


Good Luck

 

[trilobyte]

^^

isn't that what I was doing w/ longest path?

 

[trilobyte]

bump and *sigh*

 

[ant80]

Well, with the longest path, you would return the maximum. With the shortest path, you have to do the minimum. Let me know if u r having any trouble.

 

[Reel]

For longest path, I think you guys have the algorithm down. I think with shortest path, you'd just return the value of the height at the first leaf node you encounter.

if left_child == null && right_child == null
return height

 

[trilobyte]

so what would the total recursive funtion look like and how would it work? I'm having a hard time picturing this in my head.

 

[michaelh20]

Here's a related little question for you guys:

If a person tries to make an Iterator for a Binary Tree as above, I know you can do a recursive version w/
something like :


printTree(TreeNode x){

if (x == null) return;

if (x.hasLeft()) printTree(x.left());

System.out.println(x.data);

if (x.hasRight()) printTree(x.right());


}

how do you do a non recursive version?

I would figure you have to start from the lowest leaf on the left and work way up..

 

[m0ti]

You're problem is that you don't differentiate for a leaf!

Take a look at the following tree (yes this won't format correctly)

A -> B, C
C is the root of a full binary tree of depth 10.
B is the root of a long strand of depth 11 (i.e. there only exist right nodes).

You're code will indeed return a depth of 2.

The correct thing to do is:

if (ptr == null) return 0;

if (ptr->left == null && ptr->right == null) return 0;

if (ptr->left == null) return 1 + long(ptr->right);

if (ptr->right == null) return 1 + long(ptr->left);

return 1 + min(long(ptr->left), long(ptr->right));

There you go. Just have to make sure that you're at a leaf!

 

[Reel]

trilobyte: m0ti's code implements my suggestion well.

 

[trilobyte]

Wow, thanks a bunch guys (especially to m0ti and ReelC00L). The algo seems to work when I threw it in a test program. I guess my problem is just trying to trace it down and break it apart. I'm not very experienced with recursion, so it's a pain for me to figure out binary tree algo's (i'm still not 100% on how this one works...working on it though) Anyone have any tips with recursion, or is it mainly just something you learn through experience? My exam wed will most definatly have something like this :/

 

[Reel]

The way my teacher taught us recursion is this:

You need to isolate the base case(s). In this situation, the node being checked is a leaf node (i.e. it has no children at all) would be the base case since the first time you arrive at that condition, you have the minimum path.

You could also consider an invalid argument (not a binary tree node or a null node) to be a base case as well but I would have handled it before going into the recursive stepping just so it doesn't need to check for these conditions every iteration. However, it works fine being in the recursive stepping as well since it should not appear after the first iteration.

This situation has three conditions for recursive steps: a node with a left child and no right child, a node with no left child and a right child, a node with both a right child and a left child. You need to handle each of those and set it to recurse on each of those where there is a child.

Using m0ti's code, here is how I would classify it:

if (ptr == null) return 0;

check for invalid argument

if (ptr->left == null && ptr->right == null) return 0;

check for base case

if (ptr->left == null) return 1 + long(ptr->right);

if (ptr->right == null) return 1 + long(ptr->left);

return 1 + min(long(ptr->left), long(ptr->right));

recursive steps handled appropriately

 

[m0ti]

alternatively, a more intuitive approach:

if (ptr == null) return infinity; // error! infinity defined as MAX_INT for example, or MAX_LONG_INT.

if (ptr->left == null && ptr->right == null) return 0; // leaf

return 1 + min(long(ptr->left), long(ptr->right)); // non-leaf. if a son is null it will return infinity.