# BinarySearchTree getNumberOfInteriorNodes Method Help

• 04-09-2013, 05:12 PM
v1ru5
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:

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 :/
• 04-09-2013, 05:41 PM
JosAH
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
• 04-09-2013, 06:08 PM
v1ru5
Re: BinarySearchTree getNumberOfInteriorNodes Method Help
Quote:

Originally Posted by JosAH
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?
• 04-09-2013, 06:25 PM
v1ru5
Re: BinarySearchTree getNumberOfInteriorNodes Method Help
So this is how I tried to implement what you stated above.

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

Quote:

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.
• 04-09-2013, 06:30 PM
v1ru5
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.
• 04-09-2013, 07:50 PM
JosAH
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
• 04-09-2013, 08:12 PM
v1ru5
Re: BinarySearchTree getNumberOfInteriorNodes Method Help
Quote:

Originally Posted by JosAH
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 :)