[WickedBetrayal]

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.

[m-e-g-a-z]

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

[WickedBetrayal]

But if I make it 0 it gives an error.

[WickedBetrayal]

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

[macosxnerd101]

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?

[WickedBetrayal]

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));
  }
}

[macosxnerd101]

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.

[WickedBetrayal]

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?

[macosxnerd101]

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;
    }
  }

[WickedBetrayal]

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

[macosxnerd101]

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

[WickedBetrayal]

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

[macosxnerd101]

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
     -Add input to the Tree
     -Get Input
end while

[WickedBetrayal]

i did not see your post.

Thanks.

I understand why

[macosxnerd101]

Glad I could help!