Count nodes with left edge in a tree

Question

I have to implement a recursive method that counts the number of tree nodes on the left. So far my code is:

private int countLeftNodes(IntTreeNode node){ int c = 0; if (node != null){ c = 1 + countLeftNodes(node.left); countLeftNodes(node.right); } return c; } 

It returns a number much smaller than it should be. I have the feeling that my traversal is disabled because it seems to only count the leftmost child nodes and then completes. When I call this method on IntTree of size 16, I have to get 8 left child nodes, 7 right child nodes and one root, but instead I get 4 left child nodes.

Answer 1

You never count the left nodes in the right tree.

 private int countLeftNodes(IntTreeNode node) { int c = 0; if (node.left != null) { c += 1 + countLeftNodes(node.left); } if(node.right != null) { c += countLeftNodes(node.right); } return c; } 

Answer 2

To count left-child nodes, you can:

 private int countLeftNodes(IntTreeNode node) { // no tree no left-child nodes if(node == null) { return 0; } // left-child count of current node. int c = 0; // does the current node have a left-child ? if (node.left != null){ c = 1; } // return left-child count of current node + // left-child count of left and right subtrees return c + countLeftNodes(node.left) + countLeftNodes(node.right); } 

Answer 3

 private int countLeftNodes(IntTreeNode node){ int c = 0; if (node != null){ if(node.left!=null) { c = 1 + countLeftNodes(node.left); } if(node.right!=null){ c +=countLeftNodes(node.right); } } return c; } 

Answer 4

The easiest way is to check what is in the parent.

 private int countLeftNodes(IntTreeNode node){ int c = 0; if(node.left != null) { c++; c+= countLeftNodes(node.left) } if(node.right != null) { c+= countLeftNodes(node.right); } return c; } 

Answer 5

My favorite style when using recursion is to use some kind of wrapper function where the main method calls another that does the grunt job:

 private int countLeftNodes(IntTreeNode node){ int totalCount = reallyCountLeftNodes(IntTreeNode node, 0); return totalCount; } private int reallyCountLeftNodes(IntTreeNode n, Int sum){ if (n.left == NULL && n.right == NULL){ //check if we've hit rock bottom return sum; } else if (n.left == NULL) { //if the node left is nil, go right reallyCountLeftNodes(n.right, sum++); } else { reallyCountLeftNodes(n.left, sum++); // Going as far left as possible! } } 

Notice how the main function calls another. I think this style is cleaner and more understandable. In addition, the second function has a count variable that you can use.