Thread: Problem counting leaves in a tree.

1. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
8 Problem counting leaves in a tree.

I need to determine if there exists a root to leaf path with a sum equal to a number to query. I think I can determine how to do it if I knew how many leaves there are, but my code is returning the wrong number.

Java Code:
public int countLeaves()
{

if (left != null){
left.countLeaves( );}

if (right != null){
right.countLeaves( );}
if(right == null && left == null)
{
numLeaves++;
}

return numLeaves;

}
Here is the rest of the source with the main method and the Node class. The above is included in the Node class.

Java Code:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
/**
*
* 	What Works: I can strip the number from the beginning of the String, and put it into a variable.
*
* 	What doesn't work: I cannot make the actual tree itself.
*
*
* @author Bryan
*
*/

public class Tree {

static int Operand,SubStringIndex,SIndex = 0,numItems; //Used with the Separator method.
static int Index = 0,secondIndex = Index+1;  //Used with the stack
static BTNode<Integer> root; //Used to keep reference to the root of the tree.
static Stack<BTNode<Integer>> superStack = new Stack<BTNode<Integer>>();

public static void main(String[] args) throws FileNotFoundException
{
Scanner FileReader = new Scanner(new File("simpletree.txt"));
String input = FileReader.nextLine();

String treeText = Separator(input);

System.out.println("The String stripped of its operand " + treeText);
System.out.println("The Operand to search for " + Operand);
Insert(treeText);

System.out.print("Pre Order:\n"); root.preorderPrint();
System.out.print("In Order:\n"); root.inorderPrint();
System.out.print("Post Order:\n"); root.postorderPrint();
//root.print((int)BTNode.treeSize(root));

PathTester(root);

}

//Strips out the number to test, and returns the string to be inserted into the tree.
public static String Separator(String input)
{
while(input.charAt(SIndex) != '(')
{
SubStringIndex++;
SIndex++;
}
//System.out.println(SubStringIndex);
Operand = Integer.parseInt(input.substring(0,SubStringIndex));
return input.substring(SubStringIndex);
}

public static void Insert(String input)
{
while(secondIndex < input.length())
{

//Covers (# and ()
if(input.charAt(Index) == '(') //First character is a (
{
if(input.charAt(secondIndex) == '0' || input.charAt(secondIndex) == '1' || input.charAt(secondIndex) == '2' || input.charAt(secondIndex) == '3' || input.charAt(secondIndex) == '4' || input.charAt(secondIndex) == '5' || input.charAt(secondIndex) == '6'
|| input.charAt(secondIndex) == '7' || input.charAt(secondIndex) == '8' || input.charAt(secondIndex) == '9')
{

Character charNumTBI = input.charAt(secondIndex);
String numTobeInserted = charNumTBI.toString();
secondIndex ++;
Index++;
while(input.charAt(secondIndex) != '(' && input.charAt(secondIndex) != ')' )//If the second Index is a number, add that number to the insertion string.
{
numTobeInserted += input.toString().charAt(secondIndex);
secondIndex++;
Index++;
}

//System.out.println("Number to be inserted " + numTobeInserted);
int numberForm = Integer.parseInt(numTobeInserted);
if(superStack.isEmpty())
{
BTNode<Integer> alpha = new BTNode<Integer>(numberForm,null,null);
superStack.push(alpha); //If the stack is empty, make a new Node, and push it to the top of the stack.
root = alpha;
}

else if(superStack.peek().getLeft() == null && superStack.peek().isLeftNull() == false)
{
BTNode<Integer> set = new BTNode<Integer>(numberForm,null,null); //Make a new node with the data and left and right null.
superStack.peek().setLeft(set); //Set the left pointer of the top node in the stack to the newly created Node.
superStack.push(set); //Push the newly created Node to the to of the stack.
}

else if (superStack.peek().getRight() == null && superStack.peek().isRightNull() == false)
{

BTNode<Integer> set = new BTNode<Integer>(numberForm,null,null);
superStack.peek().setRight(set);
superStack.push(set);
}

else System.err.println("There was en error");

}

else if(input.charAt(secondIndex) == ')') //Left Parenthesis followed by a right parenthesis
{
if(superStack.peek().getLeft() == null)
{
//superStack.peek().setLeft(null);
superStack.peek().setLeftNull(true);

}

else
{

superStack.peek().setRight(null);
superStack.peek().setRightNull(true);
}
Index++;
secondIndex++;

//System.out.println("left pointer of " + superStack.peek().getData() + " is " + superStack.peek().getLeft());
//System.out.println("right pointer of " + superStack.peek().getData() + " is " + superStack.peek().getRight());
}
//Index++;
//secondIndex++;

}

else if(input.charAt(Index) == ')') //If the first character is a )
{

if(input.charAt(secondIndex) == ')') //followed by a )
{
superStack.pop();
}

Index++;
secondIndex++;
}

else if(input.charAt(Index) != '(' && input.charAt(Index) != ')')
{
if(input.charAt(secondIndex) == ')')
{
superStack.pop();
}

Index++;
secondIndex++;
}

} // end of while loop.

}

public static void PathTester(BTNode<Integer> root)
{
//System.out.println("Peruse Left: " + root.peruseLeft());
//System.out.println("Peruse Right: " + root.peruseRight());
System.out.println("Sum: " + root.summary());
System.out.println("Leaves: " + root.countLeaves());
}

}
Java Code:
// File: BTNode.java from the package edu.colorado.nodes
// Complete documentation is available from the BTNode link in:

/******************************************************************************
* A <CODE>BTNode&lt;<E&gt;</CODE> provides a node for a binary tree. Each node
* contains a piece of data (which is a reference to an E object) and references
* to a left and right child. The references to children may be null to indicate
* that there is no child. The reference stored in a node can also be null.
*
* <dl><dt><b>Limitations:</b> <dd>
*   Beyond <CODE>Int.MAX_VALUE</CODE> elements, <CODE>treeSize</CODE>, is
*   wrong.
*
* <dt><b>Java Source Code for this class:</b><dd>
*
* @author Michael Main
*
* @version
*   Jul 22, 2005
******************************************************************************/
public class BTNode<E>
{
// Invariant of the BTNode<E> class:
//   1. Each node has one reference to an E Object, stored in the instance
//      variable data.
//   2. The instance variables left and right are references to the node's
//      left and right children.
private E data;
private BTNode<E> left, right;
private int sum = 0,numLeaves = 0;
private Boolean leftNull = false;
private Boolean rightNull = false;

/**
* Initialize a <CODE>BTNode</CODE> with a specified initial data and links
* children. Note that a child link may be the null reference,
* which indicates that the new node does not have that child.
* @param <CODE>initialData</CODE>
*   the initial data of this new node
* @param <CODE>initialLeft</CODE>
*   a reference to the left child of this new node--this reference may be null
*   to indicate that there is no node after this new node.
* @param <CODE>initialRight</CODE>
*   a reference to the right child of this new node--this reference may be null
*   to indicate that there is no node after this new node.
* <dt><b>Postcondition:</b><dd>
*   This node contains the specified data and links to its children.
**/
public BTNode(E initialData, BTNode<E> initialLeft, BTNode<E> initialRight)
{
data = initialData;
left = initialLeft;
right = initialRight;
}

/**
* Accessor method to get the data from this node.
* @param - none
* @return
*   the data from this node
**/
public E getData( )
{
return data;
}

/**
* Accessor method to get a reference to the left child of this node.
* @param - none
* @return
*   a reference to the left child of this node (or the null reference if there
*   is no left child)
**/
public BTNode<E> getLeft( )
{
return left;
}

/**
* Accessor method to get the data from the leftmost node of the tree below
* this node.
* @param - none
* @return
*   the data from the deepest node that can be reached from this node by
*   following left links.
**/
public E getLeftmostData( )
{
if (left == null)
return data;
else
return left.getLeftmostData( );
}

/**
* Accessor method to get a reference to the right child of this node.
* @param - none
* @return
*   a reference to the right child of this node (or the null reference if there
*   is no right child)
**/
public BTNode<E> getRight( )
{
return right;
}

/**
* Accessor method to get the data from the rightmost node of the tree below
* this node.
* @param - none
* @return
*   the data from the deepest node that can be reached from this node by
*   following right links.
**/
public E getRightmostData( )
{
if (left == null)
return data;
else
return left.getRightmostData( );
}

/**
* Uses an inorder traversal to print the data from each node at or below
* this node of the binary tree.
* @param - none
* <dt><b>Postcondition:</b><dd>
*   The data of this node and all its descendants have been writeen by
*   <CODE>System.out.println( )</CODE> using an inorder traversal.
**/
public void inorderPrint( )
{
if (left != null)
left.inorderPrint( );
System.out.println(data);
if (right != null)
right.inorderPrint( );
}

/**
* Accessor method to determine whether a node is a leaf.
* @param - none
* @return
*   <CODE>true</CODE> (if this node is a leaf) or
*   <CODE>false</CODE> (if this node is not a leaf.
**/
public boolean isLeaf()
{
return (left == null && right == null);
}

public int countLeaves()
{

if (left != null){
left.countLeaves( );}

if (right != null){
right.countLeaves( );}
if(right == null && left == null)
{
numLeaves++;
}

return numLeaves;

}

/**
* Uses a preorder traversal to print the data from each node at or below
* this node of the binary tree.
* @param - none
* <dt><b>Postcondition:</b><dd>
*   The data of this node and all its descendants have been writeen by
*   <CODE>System.out.println( )</CODE> using a preorder traversal.
**/
public void preorderPrint( )
{
System.out.println(data);
if (left != null)
left.preorderPrint( );
if (right != null)
right.preorderPrint( );
}

public int summary()
{
int sum = (Integer)data;
boolean isleaf = isLeaf();
if(isleaf)
{
return sum;
}
if (left != null){
return sum + left.summary( );
}
else{

return sum + right.summary( );
}

}

/**
* Uses a postorder traversal to print the data from each node at or below
* this node of the binary tree.
* @param - none
* <dt><b>Postcondition:</b><dd>
*   The data of this node and all its descendants have been writeen by
*   <CODE>System.out.println( )</CODE> using a postorder traversal.
**/
public void postorderPrint( )
{
if (left != null)
left.postorderPrint( );
if (right != null)
right.postorderPrint( );
System.out.println(data);
}

public int peruseLeft()
{
if(left == null){sum = 0; return (Integer)data;}

else{
return sum += (Integer)left.peruseLeft(); }
}

public int peruseRight()
{

if(right == null && left == null){return (Integer)data;}

else if(right != null){
return (Integer)data + right.peruseRight(); }

else if(left != null) {
return (Integer)data + (Integer)left.peruseRight(); }

else return 0;
}

/**
* Uses an inorder traversal to print the data from each node at or below
* this node of the binary tree, with indentations to indicate the depth
* of each node.
* @param <CODE>depth</CODE>
*   the depth of this node (with 0 for root, 1 for the root's
*   children, and so on)(
* <dt><b>Precondition:</b><dd>
*   <CODE>depth</CODE> is the depth of this node.
* <dt><b>Postcondition:</b><dd>
*   The data of this node and all its descendants have been writeen by
*   <CODE>System.out.println( )</CODE> using an inorder traversal.
*   The indentation of each line of data is four times its depth in the
*   tree. A dash "--" is printed at any place where a child has no
*   sibling.
**/
public void print(int depth)
{
int i;

// Print the indentation and the data from the current node:
for (i = 1; i <= depth; i++)
System.out.print("    ");
System.out.println(data);

// Print the left subtree (or a dash if there is a right child and no left child)
if (left != null)
left.print(depth+1);
else if (right != null)
{
for (i = 1; i <= depth+1; i++)
System.out.print("    ");
System.out.println("--");
}

// Print the right subtree (or a dash if there is a left child and no left child)
if (right != null)
right.print(depth+1);
else if (left != null)
{
for (i = 1; i <= depth+1; i++)
System.out.print("    ");
System.out.println("--");
}
}

/**
* Remove the leftmost most node of the tree with this node as its root.
* @param - none
* <dt><b>Postcondition:</b><dd>
*   The tree starting at this node has had its leftmost node removed (i.e.,
*   the deepest node that can be reached by following left links). The
*   return value is a reference to the root of the new (smaller) tree.
*   This return value could be null if the original tree had only one
*   node (since that one node has now been removed).
**/
public BTNode<E> removeLeftmost( )
{
if (left == null)
return right;
else
{
left = left.removeLeftmost( );
return this;
}
}

/**
* Remove the rightmost most node of the tree with this node as its root.
* @param - none
* <dt><b>Postcondition:</b><dd>
*   The tree starting at this node has had its rightmost node removed (i.e.,
*   the deepest node that can be reached by following right links). The
*   return value is a reference to the root of the new (smaller) tree.
*   This return value could be null if the original tree had only one
*   node (since that one node has now been removed).
**/
public BTNode<E> removeRightmost( )
{
if (right == null)
return left;
else
{
right = right.removeRightmost( );
return this;
}
}

/**
* Modification method to set the data in this node.
* @param <CODE>newData</CODE>
*   the new data to place in this node
* <dt><b>Postcondition:</b><dd>
*   The data of this node has been set to <CODE>newData</CODE>.
**/
public void setData(E newData)
{
data = newData;
}

/**
* Modification method to set the link to the left child of this node.
* @param <CODE>newLeft</CODE>
*   a reference to the node that should appear as the left child of this node
*  (or the null reference if there is no left child for this node)
* <dt><b>Postcondition:</b><dd>
*   The link to the left child of this node has been set to <CODE>newLeft</CODE>.
*   Any other node (that used to be the left child) is no longer connected to
*   this node.
**/
public void setLeft(BTNode<E> newLeft)
{
left = newLeft;
}

/**
* Modification method to set the link to the right child of this node.
* @param <CODE>newLeft</CODE>
*   a reference to the node that should appear as the right child of this node
*  (or the null reference if there is no right child for this node)
* <dt><b>Postcondition:</b><dd>
*   The link to the right child of this node has been set to <CODE>newRight</CODE>.
*   Any other node (that used to be the right child) is no longer connected to
*   this node.
**/
public void setRight(BTNode<E> newRight)
{
right = newRight;
}

/**
* Copy a binary tree.
* @param <CODE>source</CODE>
*   a reference to the root of a binary tree that will be copied (which may be
*   an empty tree where <CODE>source</CODE> is null)
* @return
*   The method has made a copy of the binary tree starting at
*   <CODE>source</CODE>. The return value is a reference to the root of the copy.
* @exception OutOfMemoryError
*   Indicates that there is insufficient memory for the new tree.
**/
public static <E> BTNode<E> treeCopy(BTNode<E> source)
{
BTNode<E> leftCopy, rightCopy;

if (source == null)
return null;
else
{
leftCopy = treeCopy(source.left);
rightCopy = treeCopy(source.right);
return new BTNode<E>(source.data, leftCopy, rightCopy);
}
}

/**
* Count the number of nodes in a binary tree.
* @param <CODE>root</CODE>
*   a reference to the root of a binary tree (which may be
*   an empty tree where <CODE>source</CODE> is null)
* @return
*   the number of nodes in the binary tree
* <dt><b>Note:</b><dd>
*   A wrong answer occurs for trees larger than
*   <CODE>INT.MAX_VALUE</CODE>.
**/
public static <E> long treeSize(BTNode<E> root)
{
if (root == null)
return 0;
else
return 1 + treeSize(root.left) + treeSize(root.right);
}

public void setLeftNull(Boolean isNull)
{
leftNull = isNull;
}

public void setRightNull(Boolean isNull)
{
rightNull = isNull;
}

public Boolean isLeftNull()
{
return leftNull;
}

public Boolean isRightNull()
{
return rightNull;
}

}
Thanks for any help.  Reply With Quote

2. Re: Problem counting leaves in a tree.

The first issue I have is that your countLeaves method returns a value yet here
Java Code:
left.countLeaves( );
and here
Java Code:
right.countLeaves( );
you do nothing with those returned values. The main issue though is that you are not making a recursive call. The two lines above are calling the countLeaves methods in completely different objects which have their own separate numLeaves variables.  Reply With Quote

3. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
8 Re: Problem counting leaves in a tree.

Ok, I got it to print it out. I feel like I still need to work on recursion a bit more.

Java Code:
public int countLeaves()
{

if (left != null){
numLeaves += left.countLeaves( );}

if (right != null){
numLeaves += right.countLeaves( );}
if(right == null && left == null)
{
numLeaves++;
}

return numLeaves;

}
If possible, could you test it with the following trees? Here is an explanation on their format.

Java Code:
15(5(4(5)(6))(2()(8)))
20(10(8(6)(4))(3()(5(2)(1))))
Last edited by Wnt2bsleepin; 05-10-2012 at 03:15 AM.  Reply With Quote

4. Re: Problem counting leaves in a tree. Originally Posted by Wnt2bsleepin I feel like I still need to work on recursion a bit more.
Yes, since your revised code stuill is not recursive.

If possible, could you test it with the following trees?
Are you serious? It is your assignment not ours.  Reply With Quote

5. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
8 Re: Problem counting leaves in a tree. Originally Posted by Junky Yes, since your revised code stuill is not recursive.

Are you serious? It is your assignment not ours.
Just asking. I've had no problem testing other people's code in the past. How is it not recursive? It makes a call to itself.  Reply With Quote

6. Re: Problem counting leaves in a tree. Originally Posted by Wnt2bsleepin How is it not recursive? It makes a call to itself.
No it doesn't. As I stated above your code calls completely different methods in completely different objects. If your code was recursive it would not have "left" or "right" in front of the method calls.  Reply With Quote

7. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
8 Re: Problem counting leaves in a tree.

I think I understand where you're coming from. Sorry if I came of as wanting to be spoon fed, I just wanted a second opinion.

Java Code:
public int countLeaves(BTNode<E> root)
{
int numLeaves = 0;
if(root.getRight() == null && root.getLeft() == null)
{
numLeaves++;
}

if (root.getLeft() != null){
numLeaves += countLeaves(root.getLeft());}

if (root.getRight() != null){
numLeaves += countLeaves(root.getRight());}

return numLeaves;

}
This follows more closely with the recursive I was taught. Making the arguments smaller until you reach a base case.
Last edited by Wnt2bsleepin; 05-10-2012 at 04:17 AM.  Reply With Quote

8. Re: Problem counting leaves in a tree.

Like Junky's been trying to tell you, that's not recursion.

db  Reply With Quote

9. Senior Member Join Date
Feb 2012
Posts
219
Rep Power
8 Re: Problem counting leaves in a tree.

Is it because it is calling the method in a different instance of the BTNode class? So it's technically calling a different method even though they share the same name?  Reply With Quote

10. Re: Problem counting leaves in a tree. Originally Posted by DarrylBurke Like Junky's been trying to tell you, that's not recursion.
Enlighten me on this rainy Thursday (type slowly while I prepare my espresso ;-)

kind regards,

Jos  Reply With Quote

11. Re: Problem counting leaves in a tree.

The code in the method isn't invoking the same method, it's invoking the method on another instance of the same class.

Does that classify as a recursive call?

db <-- self and forum taught  Reply With Quote

12. Re: Problem counting leaves in a tree. Originally Posted by DarrylBurke The code in the method isn't invoking the same method, it's invoking the method on another instance of the same class.

Does that classify as a recursive call?

db <-- self and forum taught
For me it does; it's one and the same method that's being called (by itself). I consider "on what it's called" as an extra hidden parameter.

kind regards,

Jos  Reply With Quote

13. Re: Problem counting leaves in a tree.

Thank you, Jos.

db  Reply With Quote

14. Re: Problem counting leaves in a tree. Originally Posted by DarrylBurke Thank you, Jos.

db
You're welcome.

kind regards,

Jos  Reply With Quote Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•