# Thread: BinarySearchTree getNumberOfInteriorNodes Method Help

1. Member
Join Date
Sep 2012
Posts
20
Rep Power
0

## 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. ## 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

3. Member
Join Date
Sep 2012
Posts
20
Rep Power
0

## Re: BinarySearchTree getNumberOfInteriorNodes Method Help

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?

4. Member
Join Date
Sep 2012
Posts
20
Rep Power
0

## 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());
Assert.assertEquals(0,t.getNumberOfInteriorNodes());
Assert.assertEquals(1,t.getNumberOfInteriorNodes());
Assert.assertEquals(1,t.getNumberOfInteriorNodes());
Assert.assertEquals(2,t.getNumberOfInteriorNodes());
Assert.assertEquals(3,t.getNumberOfInteriorNodes());
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. Member
Join Date
Sep 2012
Posts
20
Rep Power
0

## 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. ## 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

7. Member
Join Date
Sep 2012
Posts
20
Rep Power
0

## Re: BinarySearchTree getNumberOfInteriorNodes Method Help

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

#### Posting Permissions

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