method to count leaves of a binary tree

I am trying to come up with a method to cout the leaves of a binary tree. I think I have the right idea for my algorithm, but I keep getting stack overflow error. heres what I got:
public class Node
{
   // data members   private char data;            // the character stored in the node
   private BinaryTree left;            // left child
   private BinaryTree right;           // right child
   public Node(char d)
   {
      data = d;
      left = new BinaryTree();
      right = new BinaryTree();
   }
   public char getData() {return data;}
   public BinaryTree getLeftChild() { return left;}
   public BinaryTree getRightChild() {return right;}
   public void setData(char d) {data = d;}
   public void setLeftChild(BinaryTree l) {left = l;}
   public void setRightChild(BinaryTree r) { right = r;}
}
public class BinaryTree
{
   // data members
   private Node root;     // root of the tree

   public BinaryTree() { root = null;}
   public BinaryTree(Node n) {root = n;}
   public BinaryTree getLeft()
   {
       BinaryTree t = root.getLeftChild();
       return t;
   }

      public BinaryTree getRight()
   {
       BinaryTree t = root.getRightChild();
       return t;
   }
     public boolean emptyTree() {return (root == null);}
      public char getRoot() {return root.getData();}

     public int getSize()
   {
       if (root == null)
          return 0;
       return (getLeft().getSize() + getRight().getSize()+1);
   }

     public String toString()
    {
        if (root == null)
            return " ";
        else
            return root.getData()+ " ( " + getLeft().toString() + " )   ( "+ getRight().toString()+ " )";
    }
       

   public void insertNode(char c, int flag)
   {
       BinaryTree b;
       Node n;

       if (flag != 0 && flag != 1)
       {
          System.out.println("ILLEGAL FLAG IN OPERATION");
          return;
       }
   
       n = new Node(c);
       if (root == null)
    {
        root = n;
    }
       else if (flag == 0)
       {
    if (root.getLeftChild().emptyTree())
        root.setLeftChild(new BinaryTree(n));
            else
                System.out.println("Left Tree Already Present");
       }
       else
       {
    if (root.getRightChild().emptyTree())
        root.setRightChild(new BinaryTree(n));
            else
                System.out.println("Right Tree Already Present");
       }

//                                                           here's the method I'm havein trouble with
 public int countLeaves(BinaryTree t)
    {
       int count = 0;
      if(t.root == null)
        return 0;
   
        if(t.root.getLeftChild() == null && t.root.getRightChild() == null)
          System.out.println("im a leaf!");
        count++;
        if(t.getLeft() != null)
          t.getLeft().countLeaves(t);
        if(t.getRight() != null)
          t.getRight().countLeaves(t);
        System.out.println(t.getRoot());
   
      return count;

   }

this only works for empty trees
DAJonesAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

petmagdyCommented:
obvoiusly the reason is clear ur function countLeaves(BinaryTree t) is recursing for ever because u r keeping passing the same object every time, actually ur class should look like something like  this:


 public int countLeaves()
    {
       int count = 0;
      if(t.root == null)
        return 0;
   
        if(root.getLeftChild() == null && root.getRightChild() == null)
          System.out.println("im a leaf!");
        count++;
        if(getLeft() != null)
          getLeft().countLeaves();
        if(getRight() != null)
          getRight().countLeaves();
        System.out.println(getRoot());
   
      return count;

   }

try this
0
petmagdyCommented:
miss teppoo correction:

>>, actually ur class should look like something like  this:

i mean :

, actually ur method should look like something like  this:


0
petmagdyCommented:
another important correction the method is like this:

 public int countLeaves()
    {
       int count = 0;
      if(t.root == null)
        return 0;
   
        if(root.getLeftChild() == null && root.getRightChild() == null)
          System.out.println("im a leaf!");
        count++;
        if(getLeft() != null)
          count += getLeft().countLeaves();
        if(getRight() != null)
          count += getRight().countLeaves();
        System.out.println(getRoot());
   
      return count;

   }
0
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

petmagdyCommented:
sorry a last correction:

 public int countLeaves()
    {
       int count = 0;
      if(t.root == null)
        return 0;
   
        if(root.getLeftChild() == null && root.getRightChild() == null)
        {
          System.out.println("im a leaf!");
          return 1;
        }
        if(getLeft() != null)
          count += getLeft().countLeaves();
        if(getRight() != null)
          count += getRight().countLeaves();
        System.out.println(getRoot());
   
      return count;

   }

0
DAJonesAuthor Commented:
It still gives me the stack overflow. heres my test code:
public class treeTest
{
  public static void main(String[] args)
  {
    System.out.println("creating a binary tree...");
    BinaryTree t = new BinaryTree();
    BinaryTree t1 = new BinaryTree();
    System.out.println();
    System.out.println("inserting Nodes...");
    t.insertNode('A', 0);
    t.insertNode('C', 0);
    t.insertNode('b', 1);
    t.getLeft().insertNode('D', 0);
    t.getLeft().getLeft().insertNode('A', 0);
    t.getLeft().getLeft().insertNode('V', 1);
    t.getRight().insertNode('A', 1);
    t.getRight().getRight().insertNode('b', 1);
    System.out.println(t);
    t1.insertNode('a', 0);
  //  System.out.println(t.countLeaves(t1));
    System.out.println();
    t.countLeaves(t1);
  }
}
and the out put:
> java treeTest

creating a binary tree...
inserting Nodes...
A ( C ( D ( A (   )   (   ) )   ( V (   )   (   ) ) )   (   ) )   ( b (   )   ( A (   )   ( b (   )   (   ) ) ) )

java.lang.StackOverflowError:

  at BinaryTree.countLeaves(BinaryTree.java:133)
0
petmagdyCommented:
did u applied my last comment? I still see the function has parameter
0
DAJonesAuthor Commented:
Sorry, I took out the argument, and removed all the "t." 's my stack overflow is cured, but mt output count is 0, and it should be 3
0
petmagdyCommented:
I think u didn't apply all my comments, please post the current code of  countLeaves() function
0
DAJonesAuthor Commented:
public int countLeaves()
    {
       int count = 0;
      if(root == null)
        return 0;
   
      if(root.getLeftChild() == null && root.getRightChild() == null){
          System.out.println("im a leaf!");
        return 1;
      }
        if(getLeft() != null)
        count +=  getLeft().countLeaves();
        if(getRight() != null)
         count += getRight().countLeaves();
        //System.out.print(getRoot() + " ");
   
      return count;
    }
0
petmagdyCommented:
ok give me 10 minutes I will try it


0
petmagdyCommented:
ok i tried and know it return 3, here is the correct version:

    public int countLeaves() {
        int count = 0;
        if (emptyTree())
        {
            return 0;            
        }

        if (getLeft().emptyTree()  && getRight().emptyTree() ) {
            System.out.println("im a leaf!");
            return 1;
        }
        if (getLeft() != null)
            count += getLeft().countLeaves();
        if (getRight() != null)
            count += getRight().countLeaves();
        //System.out.print(getRoot() + " ");

        return count;
    }
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
DAJonesAuthor Commented:
Ah yes!!!!! thank you sooooooo much
and in the proccess, you helped me figue out my print post order problem
have a great one!
DAJones
0
petmagdyCommented:
welcome :-)
0
DAJonesAuthor Commented:
its hardd to believe the using the emptyTree method instead of getLeft == null etc would make the difference but it does
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.