asked on

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

petmagdy

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

petmagdy

miss teppoo correction:

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

i mean :

, actually ur method should look like something like this:

petmagdy

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;

}

petmagdy

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;

}

DAJones

ASKER

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)

petmagdy

did u applied my last comment? I still see the function has parameter

DAJones

ASKER

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

petmagdy

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

DAJones

ASKER

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

petmagdy

ok give me 10 minutes I will try it

ASKER CERTIFIED SOLUTION

petmagdy

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

DAJones

ASKER

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

petmagdy

welcome :-)

DAJones

ASKER

its hardd to believe the using the emptyTree method instead of getLeft == null etc would make the difference but it does