Count number of left nodes in BST

Question

Given a BST, I am required to find the number of left nodes of the tree.

Example: `

          +---+
          | 3 |
          +---+
         /     \
     +---+     +---+
     | 5 |     | 2 |
     +---+     +---+
    /         /     \
+---+     +---+     +---+
| 1 |     | 4 |     | 6 |
+---+     +---+     +---+
         /
     +---+
     | 7 |
     +---+`

The answer should be 4, as (5, 1 , 4, 7) are all left nodes of the tree.

What I am thinking of doing is:

public int countLeftNodes() {
    return countLeftNodes(overallRoot, 0);
}

private int countLeftNodes(IntTreeNode overallRoot, int count) {
    if (overallRoot != null) {
        count += countLeftNodes(overallRoot.left, count++);    
        count = countLeftNodes(overallRoot.right, count);
    }
    return count;
}

I know it is wrong, but I don't know why. Could someone explain why, and also help me with the answer.

Answer 1

The second recursion branch overwrites the value from the first. Also you should add 1 for the left root.

Something like:

private int countLeftNodes(IntTreeNode node) {
    int count = 0;
    if (node.left != null) 
        count += 1 + countLeftNodes(node.left);    

    if (node.right != null)
        count += countLeftNodes(node.right);


    return count;
}

Answer 2

There is no need to propagate an accumulator (the count parameter) down the call stack, since you aren't relying on tail-recursion.

public int countLeftNodes(IntTreeNode node) {
    // This test is only needed if the root node can be null.
    if (node == null) return 0;

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

Answer 3

In your second line here

count += countLeftNodes(overallRoot.left, count++);    
count = countLeftNodes(overallRoot.right, count);

you discard the previous value of count. Perhaps it should be += instead of =.

I would however express it like this:

private int countLeftNodes(IntTreeNode root) {
    return (root.left  == null ? 0 : countLeftNodes(root.left) + 1) +
           (root.right == null ? 0 : countLeftNodes(root.right));
}