# Finding deepest node of tree??

• April 9th, 2011, 05:58 AM
bczm8703
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

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
• April 9th, 2011, 10:46 AM
copeg
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'
• April 9th, 2011, 11:48 PM
bczm8703
Re: Finding deepest node of tree??
sorry for asking this noobish qn.. but is it possible to post some example codes?
• April 10th, 2011, 09:46 AM
phamminh91
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.
Code :

` // edited by moderator`
• April 10th, 2011, 11:40 AM
copeg
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
• April 10th, 2011, 11:48 AM
phamminh91
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.