Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Finding deepest node of tree??

  1. #1
    Member
    Join Date
    Mar 2011
    Posts
    47
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Exclamation 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 :


    Uploaded with ImageShack.us
    the code of the deepNode is:

      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


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default 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'

  3. #3
    Member
    Join Date
    Mar 2011
    Posts
    47
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Finding deepest node of tree??

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

  4. #4
    Junior Member
    Join Date
    Apr 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Finding deepest node of tree??

    Here is my code:
    - 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.
     // edited by moderator
    Last edited by copeg; April 10th, 2011 at 11:27 AM.

  5. #5
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Finding deepest node of tree??

    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

  6. #6
    Junior Member
    Join Date
    Apr 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Finding deepest node of tree??

    Quote Originally Posted by copeg View Post
    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 .

Similar Threads

  1. Node swap (move up)
    By raphytaffy in forum What's Wrong With My Code?
    Replies: 0
    Last Post: December 2nd, 2010, 06:56 PM
  2. [SOLVED] XML get/set node by attribute value
    By b_jones10634 in forum File I/O & Other I/O Streams
    Replies: 1
    Last Post: August 24th, 2010, 11:26 AM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  4. TreeNode vs. Node
    By Kumarrrr in forum Java Theory & Questions
    Replies: 1
    Last Post: March 27th, 2010, 06:06 AM
  5. Xml-Node Retrieval
    By prasb in forum File I/O & Other I/O Streams
    Replies: 0
    Last Post: December 4th, 2009, 12:44 PM