[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

method to count leaves of a binary tree

Posted on 2004-11-21
14
Medium Priority
?
3,151 Views
Last Modified: 2008-01-09
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
0
Comment
Question by:DAJones
  • 9
  • 5
14 Comments
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639279
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
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639283
miss teppoo correction:

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

i mean :

, actually ur method should look like something like  this:


0
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639290
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 13

Expert Comment

by:petmagdy
ID: 12639301
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
 

Author Comment

by:DAJones
ID: 12639361
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
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639368
did u applied my last comment? I still see the function has parameter
0
 

Author Comment

by:DAJones
ID: 12639419
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
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639432
I think u didn't apply all my comments, please post the current code of  countLeaves() function
0
 

Author Comment

by:DAJones
ID: 12639443
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
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639486
ok give me 10 minutes I will try it


0
 
LVL 13

Accepted Solution

by:
petmagdy earned 2000 total points
ID: 12639563
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
 

Author Comment

by:DAJones
ID: 12639647
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
 
LVL 13

Expert Comment

by:petmagdy
ID: 12639653
welcome :-)
0
 

Author Comment

by:DAJones
ID: 12639654
its hardd to believe the using the emptyTree method instead of getLeft == null etc would make the difference but it does
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
In this post we will learn different types of Android Layout and some basics of an Android App.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
This video teaches viewers about errors in exception handling.
Suggested Courses
Course of the Month19 days, 5 hours left to enroll

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question