[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
Medium Priority
3,151 Views
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
}
else
{
if (root.getRightChild().emptyTree())
root.setRightChild(new BinaryTree(n));
else
}

//                                                           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
Question by:DAJones
• 9
• 5

LVL 13

Expert Comment

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

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

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

LVL 13

Expert Comment

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

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

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

Author Comment

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

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

Author Comment

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

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

0

LVL 13

Accepted Solution

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

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

ID: 12639653
welcome :-)
0

Author Comment

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

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