Results 1 to 7 of 7
  1. #1
    v1ru5 is offline Member
    Join Date
    Sep 2012
    Posts
    20
    Rep Power
    0

    Angry BinarySearchTree getNumberOfInteriorNodes Method Help

    Hi guys,

    So I was trying to make a method for a binary tree that would get the number of interior nodes(non-leaf nodes or nodes who have no children). This is how I attempted to implement it but it was not working. It would be great if someone could help me here:

    Java Code:
    Node<E> current = root;
      public int getNumberOfInteriorNodes() {
        int count = 0;
        if (root==null||root.right==null||root.left==null)
          return 0;
        if (current.right.value==null&&current.left.value==null){
          return count;
        }
        else{
        if (current.right.value!=null){
          count++;
          current=current.right;
          getNumberOfInteriorNodes();
    }
        if (current.left.value!=null){
          count++;
          current=current.left;
          getNumberOfInteriorNodes();
        }
        }
        return count;
    }
    Ive been trying to get this to work for a couple of hours now, I am still stuck :/

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,453
    Blog Entries
    7
    Rep Power
    20

    Default Re: BinarySearchTree getNumberOfInteriorNodes Method Help

    If there are no nodes (root == null) or both of its children are null, the result is 0. Otherwise, the current node is an internal node, so the result is 1+count(root.left)+count(root.right).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    v1ru5 is offline Member
    Join Date
    Sep 2012
    Posts
    20
    Rep Power
    0

    Default Re: BinarySearchTree getNumberOfInteriorNodes Method Help

    Quote Originally Posted by JosAH View Post
    If there are no nodes (root == null) or both of its children are null, the result is 0. Otherwise, the current node is an internal node, so the result is 1+count(root.left)+count(root.right).

    kind regards,

    Jos
    Thanks for the reply! The recursive part is where I was getting confused because my method does not have any input parameters so I cannot do 1+count(root.left)+count(root.right). What can I do instead of this?

  4. #4
    v1ru5 is offline Member
    Join Date
    Sep 2012
    Posts
    20
    Rep Power
    0

    Default Re: BinarySearchTree getNumberOfInteriorNodes Method Help

    So this is how I tried to implement what you stated above.

    Java Code:
    Node<E> current = root;
      public int getNumberOfInteriorNodes() {
        int count==0;;
        if (current==null||root==null||(current.left==null&&current.right==null)){
          return count;
        }
        else{
          if (current.right!=null){
            current=current.right;
          return count+=1+getNumberOfInteriorNodes();
          }
          if (current.left!=null){
            current=current.left;
            return count+=1+getNumberOfInteriorNodes();
        }
    }
        return count;
    }
    Below is what the test case looks like:
    Java Code:
    public static void testGetNumberOfInteriorNodes() {
    
         BinarySearchTree<Integer> t;
         t = new BinarySearchTree<Integer>();
         Assert.assertEquals(0,t.getNumberOfInteriorNodes());
         t.add(2);
         Assert.assertEquals(0,t.getNumberOfInteriorNodes());
         t.add(1);
         Assert.assertEquals(1,t.getNumberOfInteriorNodes());
         t.add(5);
         Assert.assertEquals(1,t.getNumberOfInteriorNodes());
         t.add(4);
         Assert.assertEquals(2,t.getNumberOfInteriorNodes());
         t.add(3);
         Assert.assertEquals(3,t.getNumberOfInteriorNodes());
         t.add(6);
         Assert.assertEquals(3,t.getNumberOfInteriorNodes());
     }
    I get an error at the 3rd assertion and this is what it says:

    Failure: junit.framework.AssertionFailedError: expected:<1> but was:<0>
    The above error is what I have been getting since the begining of time. No matter what way I try to implement this, I get the above error. Please help.

  5. #5
    v1ru5 is offline Member
    Join Date
    Sep 2012
    Posts
    20
    Rep Power
    0

    Default Re: BinarySearchTree getNumberOfInteriorNodes Method Help

    I sort of discovered the problem, count never increases, it is always 0. Trying to find how to fix this.

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,453
    Blog Entries
    7
    Rep Power
    20

    Default Re: BinarySearchTree getNumberOfInteriorNodes Method Help

    You need to pass the current node as a parameter of your recursive method; the method doesn't need a local int count variable; also see my previous reply for an (almost) definition of the recursive method:

    - if there is no node or if it is a leaf node: the result is 0
    - otherwise it is 1+count(node.left)+count(node.right)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    v1ru5 is offline Member
    Join Date
    Sep 2012
    Posts
    20
    Rep Power
    0

    Default Re: BinarySearchTree getNumberOfInteriorNodes Method Help

    Quote Originally Posted by JosAH View Post
    You need to pass the current node as a parameter of your recursive method; the method doesn't need a local int count variable; also see my previous reply for an (almost) definition of the recursive method:

    - if there is no node or if it is a leaf node: the result is 0
    - otherwise it is 1+count(node.left)+count(node.right)

    kind regards,

    Jos
    Woow thanks for your help! I did exactly what you said using a private helper method and it worked! thanks again :)

Similar Threads

  1. Replies: 2
    Last Post: 03-23-2012, 04:53 AM
  2. Replies: 1
    Last Post: 10-17-2011, 01:00 AM
  3. Problems creating a new BinarySearchTree class object
    By EnSlavingBlair in forum New To Java
    Replies: 2
    Last Post: 10-01-2011, 11:27 AM
  4. binarysearchtree problems help!
    By runachoi in forum New To Java
    Replies: 1
    Last Post: 12-03-2010, 03:35 AM
  5. Turning Recursion Method into Iterative method
    By mattakuevan in forum New To Java
    Replies: 9
    Last Post: 06-15-2010, 06:46 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •