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&¤t.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 :/

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

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?

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&¤t.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.

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.

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

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