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) && isInternal(n.right) || (isInternal(n.left) && isLeaf(n.right)));
}
/* Check if n is leaf */
private static boolean isLeaf(TreeNode n) {
return (n == null) ? false : (n.left == null && 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);
}