Finding deepest node of tree??

hi.. i have a binary search tree class which is a user defined one.. when i invoke the deepNode method some sort of logic error occur...

the tree structure is :

http://img715.imageshack.us/img715/1323/treecr.jpg

Uploaded with ImageShack.us

the code of the deepNode is:

Code :

public void deepNode()
{
if (isEmpty())return;
Queue2 q= new Queue2();
q.enqueue(root);
while (!q.isEmpty())
{
BTNode cur=(BTNode) (q.dequeue());
if (cur!=null)
{
if (cur.left!=null)
q.enqueue(cur.left);
if (cur.right!=null)
q.enqueue(cur.right);
if (cur.right==null && cur.left==null)
System.out.println(cur.item);
}
}
}

the current output is: 23, 21

the correct output should be: 21

Re: Finding deepest node of tree??

The code does not find the deepest node, but all leaf nodes - which based upon the tree posted above are 23 and 21. To find the deepest node, you need to get the depth/level as well, and find the node(s) with the highest value. Many ways to do this, possibly the easiest might be to use a recursive method which has the level value passed as a parameter, from which you can determine the 'deepest'

Re: Finding deepest node of tree??

sorry for asking this noobish qn.. but is it possible to post some example codes?

Re: Finding deepest node of tree??

Here is my code: :cool:

- First you need to find the depth/height of the tree.

- Then traverses through each node, find the current depth and compare it with the maxDepth.

- If condition satisfied, print out the item stored in the node.

Re: Finding deepest node of tree??

Quote:

sorry for asking this noobish qn.. but is it possible to post some example codes?

phamminh91 has given some great pseudo-code to begin with. Recommend you give it a go, break the problem down as phamminh91 has outlined and do this step by step...I will note that you've posted a solution using a while loop, and you may find it easier to use a recursive approach. The following link provides some great descriptions and examples to tackle the problem

Binary Trees

Re: Finding deepest node of tree??

Quote:

Originally Posted by

**copeg**
phamminh91 has given some great pseudo-code to begin with. Recommend you give it a go, break the problem down as phamminh91 has outlined and do this step by step...I will note that you've posted a solution using a while loop, and you may find it easier to use a recursive approach. The following link provides some great descriptions and examples to tackle the problem

Binary Trees

Oops, I am not supposed to post the exact code LOL :D.