Results 1 to 7 of 7
 04092013, 05:12 PM #1Member
 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(nonleaf 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==nullroot.right==nullroot.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; }
 04092013, 05:41 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,414
 Blog Entries
 7
 Rep Power
 25
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 04092013, 06:08 PM #3Member
 Join Date
 Sep 2012
 Posts
 20
 Rep Power
 0
 04092013, 06:25 PM #4Member
 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==nullroot==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; }
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()); }
Failure: junit.framework.AssertionFailedError: expected:<1> but was:<0>
 04092013, 06:30 PM #5Member
 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.
 04092013, 07:50 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,414
 Blog Entries
 7
 Rep Power
 25
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 04092013, 08:12 PM #7Member
 Join Date
 Sep 2012
 Posts
 20
 Rep Power
 0
Similar Threads

Creating recursion method to use Newton's method for square roots
By bdl1127 in forum New To JavaReplies: 2Last Post: 03232012, 05:53 AM 
Whats the different between package.class.method and super.method?
By Pojahn_M in forum New To JavaReplies: 1Last Post: 10172011, 01:00 AM 
Problems creating a new BinarySearchTree class object
By EnSlavingBlair in forum New To JavaReplies: 2Last Post: 10012011, 11:27 AM 
binarysearchtree problems help!
By runachoi in forum New To JavaReplies: 1Last Post: 12032010, 04:35 AM 
Turning Recursion Method into Iterative method
By mattakuevan in forum New To JavaReplies: 9Last Post: 06152010, 06:46 AM
Bookmarks