countNodes method for a Tree

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

39 Replies - 2017 Views - Last Post: 23 February 2011 - 06:32 PM Rate Topic: -----

#1 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • Winning
  • member icon


Reputation: 496
  • View blog
  • Posts: 1,453
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • 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?
Was This Post Helpful? 0
  • +
  • -

#6 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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));
  }
}

Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#8 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • 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. :)

View PostWickedBetrayal, 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;
    }
  }

Was This Post Helpful? 0
  • +
  • -

#10 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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

>.<
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • 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
-Add it to the Tree
-Check if it is < 10
Was This Post Helpful? 0
  • +
  • -

#12 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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??
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • 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
     -Add input to the Tree
     -Get Input
end while


Was This Post Helpful? 0
  • +
  • -

#14 WickedBetrayal  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,475
  • Joined: 27-December 08

Re: countNodes method for a Tree

Posted 22 February 2011 - 05:57 PM

Glad I could help! :)
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3