Exercise - count binary-tree nodes with 1 leaf and 1 internal node as children I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and am trying to solve one of the exercises there. 

The exercise


  Write a program that counts the amount of nodes in a binary tree, that
  have an external and an internal node as children.


In the following picture, the ones with the red dot are the ones I think I have to count. 

For simplification in the further text I dubbed these nodes "wanted nodes" and the method that determines if a node is a "wanted node" thus isWantedNode(). The solution to this is fairly straightforward if done recursively, but I can't find the most elegant one.

Requests


How can the recursion be simplified to avoid invoking methods unnecessarily in the first place? 


I currently want to focus on doing this recursively before I jump into changing this into an iterative solution, for learning purposes on my part. 

I'm certain that the recursion can be simplified, I just don't see how. The key here is to check for child-nodes being leafs or internal nodes while avoiding NullPointerExceptions when you're checking if a node is a "wanted node". My current approach is dealing with the NullPointerExceptions instead of avoiding invoking methods for null objects in the first place which I don't think is the best way to go about this. 

The Code

static class TreeNode {
        TreeNode left;
        TreeNode right;

        TreeNode(TreeNode l, TreeNode r) {
            this.left = l;
            this.right = r;
        }
    }

/* Count wanted nodes */
private static int strangeCount(TreeNode h) {
    if (h == null) {
        return 0;
    }
    int result = strangeCount(h.left) + strangeCount(h.right);
    return (isWantedNode(h)) ? result + 1 : result;
}

/* Check if n is wanted node */
private static boolean isWantedNode(TreeNode n) {
    return (isLeaf(n.left) &amp;&amp; isInternal(n.right) || (isInternal(n.left) &amp;&amp; isLeaf(n.right)));
}

/* Check if n is leaf */
private static boolean isLeaf(TreeNode n) {
    return (n == null) ? false : (n.left == null &amp;&amp; n.right == null);
}

/* Check if n is internal node */
private static boolean isInternal(TreeNode n) {
    return (n == null) ? false : (n.left != null || n.right != null);
}
Your comments arn't really helpful, and so I'd remove them. This is as the function names say all that you would want to know.
Using the inverse of 'split the line, change the sign', more commonly know as DeMorgan's laws, you can change isInternal to be much simpler. Rather than using \$\overline{A} \lor \overline{B}\$ your can use \$\overline{A \land B}\$.
Since isInternal is the inverse of isLeaf you can just check that isLeaf(n.left) is not the same as isLeaf(n.right), as if it's not then there is one leaf and one internal.


And so you can change isWantedNode and isLeaf to:

private static boolean isWantedNode(TreeNode n) {
    if (n.left == null || n.right == null)
        return false;
    return isLeaf(n.left) != isLeaf(n.right);
}

private static boolean isLeaf(TreeNode n) {
    return n.left == null &amp;&amp; n.right == null;
}


You may also want to change your return statment in strangeCount from a turnery, to addition of result and a turnery.
And so I'd use:

private static int strangeCount(TreeNode h) {
    if (h == null) {
        return 0;
    }
    return strangeCount(h.left) + strangeCount(h.right) + (isWantedNode(h)?1:0);
}