countNodes method for a Tree

• (3 Pages)
• 1
• 2
• 3

39 Replies - 3798 Views - Last Post: 23 February 2011 - 06:32 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=217809&amp;s=e74d7772fe60e542008c3bcec08ad40f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

countNodes method for a Tree

Posted 21 February 2011 - 09:59 PM

I have to make a recursive method to count nodes in a tree.

This is my code:

```public static int countNodes(BSTNode n) {
if (n==null)
return 0;
else {
int count = 1;
count += countNodes(n.left);
count += countNodes(n.right);
return count;
}
}
```

It returns a value at the end of 1 more than what the actual count is. I have no idea why.

Help?

Thanks.

Is This A Good Question/Topic? 0

Replies To: countNodes method for a Tree

#2 m-e-g-a-z

• Winning

Reputation: 497
• Posts: 1,457
• Joined: 19-October 09

Re: countNodes method for a Tree

Posted 22 February 2011 - 03:42 AM

Because your assigning count to 1 hence why you are getting an extra +1 within the total of Nodes.

#3 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 01:12 PM

But if I make it 0 it gives an error.

#4 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 01:22 PM

Actually its not an error. It just a 0. and never changes.

#5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:12 PM

Your original method looks good to me. Can you post more code so we can see how the Binary Search Tree is set up, as well as where you invoke the method?

#6 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:31 PM

Yeah, I was thinking maybe i am inserting elements wrong or something?

```public class BST<T extends Comparable<? super T>> {
protected BSTNode<T> root = null;
public BST() {
}
protected void printTree(BSTNode<T> p, int depth) {
if (p != null) {
printTree(p.right,depth+1);
for (int i = 1; i <= depth; i++)
System.out.print("     ");
System.out.println(p.el);
printTree(p.left,depth+1);
}
}
public void printTree() {
printTree(root,0);
}
public void insert(T el) {
BSTNode<T> p = root, prev=null;
while (p != null) {
prev = p;
if (el.compareTo(p.el) < 0)
p = p.left;
else p = p.right;
}
if (root == null)
root = new BSTNode<T>(el);
else if (el.compareTo(prev.el) <0)
prev.left = new BSTNode<T>(el);
else prev.right = new BSTNode<T>(el);
}
public T search(T el) {
BSTNode<T> p = root;
while (p != null)
if  (el.compareTo(p.el) == 0)
return p.el;
else if (el.compareTo(p.el) < 0)
p = p.left;
else p = p.right;
return null;
}
protected void preorder(BSTNode<T> p) {
if (p!=null) {
visit(p);
preorder(p.left);
preorder(p.right);
}
}
public void preorder() {
preorder(root);
}
protected void inorder(BSTNode<T> p) {
if (p!=null) {
inorder(p.left);
visit(p);
inorder(p.right);
}
}
public void inorder() {
inorder(root);
}
protected void postorder(BSTNode<T> p) {
if (p!=null) {
postorder(p.left);
postorder(p.right);
visit(p);
}
}
public void postorder() {
postorder(root);
}
public void visit(BSTNode<T> p) {
System.out.println(p.el + " ");
}
}
```

```public class BSTNode<T extends Comparable<? super T>> {
protected T el;
protected BSTNode<T> left, right;
BSTNode(T t, BSTNode<T> lt, BSTNode<T> rt) {
el = t;
left = lt;
right = rt;
}
BSTNode(T t) {
this(t,null,null);
}
BSTNode() {
this(null,null,null);
}
}
```

and here is my main .java file with these methods i have to make along with my main method for testing purposes:
```import java.util.Scanner;
class Homework2_24 {
public static int countLeaves(BSTNode n) {
if (n==null)
return 0;
else if (n.left==null && n.right==null)
return 1;
else {
return countLeaves(n.left)+countLeaves(n.right);
}
}
public static int countNodes(BSTNode n) {
if (n==null)
return 0;
else {
int count = 0;
count += countNodes(n.left);
count += countNodes(n.right);
return count;
}
}
static public void main(String[] a) {
BST<Integer> tree = new BST<Integer>();
int i = 1;
Scanner kb = new Scanner(System.in);

System.out.print("Enter some integers, end with 0: ");
while (i != 0) {
i = kb.nextInt();
tree.insert(i);
}
System.out.println(countLeaves(tree.root));
System.out.println(countNodes(tree.root));
}
}
```

#7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:32 PM

Rather than me dealing with user input, can you set up a Binary Search Tree and post the results you get so I can run through your code.

#8 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:42 PM

```import java.util.Scanner;
class Homework2_24 {
public static int countLeaves(BSTNode n) {
if (n==null)
return 0;
else if (n.left==null && n.right==null)
return 1;
else {
return countLeaves(n.left)+countLeaves(n.right);
}
}
public static int countNodes(BSTNode n) {
if (n==null)
return 0;
else {
int count = 0;
count += countNodes(n.left);
count += countNodes(n.right);
return count;
}
}
static public void main(String[] a) {
BST<Integer> tree = new BST<Integer>();
int i = 1;
Scanner kb = new Scanner(System.in);
tree.insert(15);
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(35);
tree.insert(25);
tree.insert(23);
tree.insert(27);
tree.insert(26);
//   System.out.print("Enter some integers, end with 0: ");
//    while (i != 0) {
//     i = kb.nextInt();
//     tree.insert(i);
}
System.out.println(countLeaves(tree.root));
System.out.println(countNodes(tree.root));
}
}
```

Like this?

#9 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:46 PM

I just ran your code using this method from your original post, and it was exactly right. It returned 9, and you had 9 elements in your Tree.

WickedBetrayal, on 21 February 2011 - 11:59 PM, said:

```public static int countNodes(BSTNode n) {
if (n==null)
return 0;
else {
int count = 1;
count += countNodes(n.left);
count += countNodes(n.right);
return count;
}
}
```

#10 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:50 PM

WHAT!!!!

dude. It says 10 for me! I do not know what to do! Could it be my user input?

That has to be it. Something is wrong. I put those elements in in the same order every time i tested it. and it gave back 10 every single time

#11 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:52 PM

You end up inserting 0 at the end, which is why it returns 10. Note you do the following in said order:
-Get input
-Check if it is < 10

#12 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:53 PM

Wow. it is.

Thanks for helping me finding some mistake i do not understand. Lol

Yep it returns 9.. Maybe it is counting my 0 to end the loop for some reason??

#13 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:54 PM

Quote

Maybe it is counting my 0 to end the loop for some reason??

That is exactly it. I would reorder your logic for user input to something along these lines to check to make sure you are adding valid input to the tree:
```-Get input
-while input > 0
-Get Input
end while

```

#14 WickedBetrayal

Reputation: 0
• Posts: 84
• Joined: 16-February 11

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:55 PM

i did not see your post.

Thanks.

I understand why

#15 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12318
• Posts: 45,417
• Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:57 PM