# Problem counting leaves in a tree.

• 05-10-2012, 02:40 AM
Wnt2bsleepin
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.

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.

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());         }                                                 }```
Code:

``` // File: BTNode.java from the package edu.colorado.nodes // Complete documentation is available from the BTNode link in: //  http://www.cs.colorado.edu/~main/docs/ /****************************************************************************** * 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> *  <A HREF="../../../../edu/colorado/nodes/BTNode.java"> *  http://www.cs.colorado.edu/~main/edu/colorado/nodes/BTNode.java </A> * * @author Michael Main *  <A HREF="mailto:main@colorado.edu"> (main@colorado.edu) </A> * * @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.
• 05-10-2012, 03:08 AM
Junky
Re: Problem counting leaves in a tree.
The first issue I have is that your countLeaves method returns a value yet here
Code:

`left.countLeaves( );`
and here
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.
• 05-10-2012, 03:12 AM
Wnt2bsleepin
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.

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.

Code:

```15(5(4(5)(6))(2()(8))) 20(10(8(6)(4))(3()(5(2)(1))))```
• 05-10-2012, 03:26 AM
Junky
Re: Problem counting leaves in a tree.
Quote:

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.
Quote:

If possible, could you test it with the following trees?
Are you serious? It is your assignment not ours.
• 05-10-2012, 03:38 AM
Wnt2bsleepin
Re: Problem counting leaves in a tree.
Quote:

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.
• 05-10-2012, 03:44 AM
Junky
Re: Problem counting leaves in a tree.
Quote:

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.
• 05-10-2012, 04:02 AM
Wnt2bsleepin
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.

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.
• 05-10-2012, 05:16 AM
DarrylBurke
Re: Problem counting leaves in a tree.
Like Junky's been trying to tell you, that's not recursion.

db
• 05-10-2012, 05:24 AM
Wnt2bsleepin
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?
• 05-10-2012, 08:29 AM
JosAH
Re: Problem counting leaves in a tree.
Quote:

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
• 05-10-2012, 08:35 AM
DarrylBurke
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
• 05-10-2012, 08:40 AM
JosAH
Re: Problem counting leaves in a tree.
Quote:

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
• 05-10-2012, 08:57 AM
DarrylBurke
Re: Problem counting leaves in a tree.
Thank you, Jos.

db
• 05-10-2012, 09:10 AM
JosAH
Re: Problem counting leaves in a tree.
Quote:

Originally Posted by DarrylBurke
Thank you, Jos.

db

You're welcome.

kind regards,

Jos