problem in the countLeaves method of a binary tree

[cool_yu2k]

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

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.

Hope this solves your problem

[kvprajapati]

Duplicate thread - http://www.daniweb.com/forums/thread205917.html

[cool_yu2k]

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

you are welcome