Hello! I have another problem in my binary tree. The countLeaves method does not output the correct answer. Instead of outputting 3, it output 1. I don't know what's the problem on the algorithm of my countLeaves method but I guess it is correct. Can anybody help me solve this problem? Thank you very much...

``````package binaryTree;

public class BinaryTree {
Object root;
int value;
BinaryTree leftSubtree;
BinaryTree rightSubtree;

public BinaryTree() {
root = null;
leftSubtree = null;
rightSubtree = null;
}

public BinaryTree(int value, BinaryTree left, BinaryTree right){
root = value;
leftSubtree = left;
rightSubtree = right;
}

public Object getRoot(){
return root;
}

public void setRoot(int root){
this.root = root;
}

public BinaryTree getLeftSubtree(){
return leftSubtree;
}

public void setLeftSubtree(BinaryTree leftSubtree){
this.leftSubtree = leftSubtree;
}

public BinaryTree getRightSubtree(){
return rightSubtree;
}

public void setRightSubtree(BinaryTree rightSubtree){
this.rightSubtree = rightSubtree;
}

public static void main(String[] args){
new BinaryTree(0).run();
}

public BinaryTree(int value) {
root=value;
leftSubtree = null;
rightSubtree = null;
this.value = value;
}

public void run() {
BinaryTree node = new BinaryTree(50);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + node.value);
insert(node, 17);
insert(node, 76);
insert(node, 54);
insert(node, 23);
insert(node, 9);
insert(node, 14);
insert(node, 19);
insert(node, 72);
insert(node, 12);
insert(node, 67);
System.out.println("\n\nHeight:");
System.out.println(getHeight(node));
System.out.println("\n\nCOUNT NODES:");
System.out.println(countNode(node));
System.out.println("\n\nCOUNT LEAVES:");
System.out.println(countLeaves(node));
System.out.println("\nTraversing tree in order:");
inorderTraversal(node);
System.out.println("\n\nTraversing tree preorder:");
preorderTraversal(node);
System.out.println("\n\nTraversing tree postorder:");
postorderTraversal(node);
}

public void insert(BinaryTree root, int value) {
if (value < root.value) {
if (root.leftSubtree != null) {
insert(root.leftSubtree, value);
} else {
System.out.println("  Inserted " + value + " to left of " + root.value);
root.leftSubtree = new BinaryTree(value);
}
} else if (value > root.value) {
if (root.rightSubtree != null) {
insert(root.rightSubtree, value);
} else {
System.out.println("  Inserted " + value + " to right of "
+ root.value);
root.rightSubtree = new BinaryTree(value);
}
}
}

public void inorderTraversal(BinaryTree root) {
if (root != null) {
inorderTraversal(root.leftSubtree);
System.out.print(root.value+" ");
inorderTraversal(root.rightSubtree);
}
}

public void preorderTraversal(BinaryTree root){
if(root !=null){
System.out.print(root.value+" ");
preorderTraversal(root.leftSubtree);
preorderTraversal(root.rightSubtree);
}
}

public void postorderTraversal(BinaryTree root){
if(root !=null){
postorderTraversal(root.leftSubtree);
postorderTraversal(root.rightSubtree);
System.out.print(root.value+" ");
}
}

public void levelorderTraversal(BinaryTree root){
if(root!=null){
}
}

public int getHeight(BinaryTree root){
if(root == null){
return 0;
}
else{
return 1 + Math.max(getHeight(root.leftSubtree),getHeight(root.rightSubtree));
}
}

public int countNode(BinaryTree root) {
if(root==null){
return 0;
}
else{
return 1 + countNode(root.leftSubtree) + countNode(root.rightSubtree);
}
}

public int countLeaves(BinaryTree root){
if(root==null){
return 0;
}
else if(leftSubtree==null && rightSubtree==null){
return 1;
}
else{
return countLeaves(root.leftSubtree) + countLeaves(root.rightSubtree);
}
}

public boolean isEmpty(){
if(root == null){
return true;
}else
return false;
}

}``````
3
Contributors
4
Replies
6
Views
8 Years
Discussion Span
Last Post by harsh2327

Obviously your countLeaves function is incorrect. It will always stop at the second if condition "if(leftSubtree==null && rightSubtree==null)" and return 1 because leftSubtree and rightSubtree is null under second call to the function.

``````public int countLeaves(BinaryTree root){
if(root==null){
return 0;
}
else if(leftSubtree==null && rightSubtree==null){
return 1;
}
else{
return countLeaves(root.leftSubtree) + countLeaves(root.rightSubtree);
}
}``````

The actual code should be

``````public int countLeaves(BinaryTree root){
if(root==null){
return 0;
}
else if(root.leftSubtree==null && root.rightSubtree==null){
return 1;
}
else{
return countLeaves(root.leftSubtree) + countLeaves(root.rightSubtree);
}
}``````

Since you are using recursion, `root.leftSubtree` and `leftSubtree` are not one ad the same.

If you use only `leftSubtree` , it is understood as `this.leftSubtree` by the compiler, which is the calling object.

Thank you very much! ^_^ I really appreciate you effort and time,sir!

you are welcome

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.