Exercise - count binary-tree nodes with 1 leaf and 1 internal node as children

Question

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

1. 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);
}

Answer 1

1. 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.
2. 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}\$.
3. 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 && 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);
}

Answer 2

Lets review some of the coding style firstly:

• All methods are private? – I'm a bit rusty in my Java, but this does seem kind of strange. OK, that they are static or class methods, as they don't rely on internal mechanisms, but private?

• Comments are slightly meaningless – That the isWantedNode checks to see if it is a wanted node, is kind of obvious. It would be better having a comment stating something like "A wanted node has one internal child node and one external (or leaf) child node".

• Very fond of ternary operations, are you? – Ternary can be a good thing, but too much of them can also be misleading and slightly confusing.

• isInternal() and isLeaf() are negated version of each other – Any leaf is not internal, and vice versa. Could use one method, or if wanting both one of them could depend on the other.

• Avoiding method calls are not always needed – Having to call an extra set of functions to make the code look clearer is not always a bad thing. Calling methods which would trigger multiple (repeated) calls down the entire tree, that is another story. Compiler nowadays are quite efficient related to knowing when they can inline methods and so on.

  And not using methods, would require either using try..catch sequences or long ugly stuff like (for the isWantedNode() left side internal):

  n != null && 
  n.left != null && n.left.left == null && n.left.right == null && 
  n.right != null && (n.right.left != null || n.right.right != null)
  

  Not very nice or easy to read. Is it?

• Static or not?! – Why is the TreeNode class static? Shouldn't that be instantiated, and just left as a normal class?

• No payload in your TreeNode – The TreeNode is not actually able to carry anything, which is kind of strange, but understandable for an exercise. But normally it would have an int or a string or something so that it had some meaning besides a tree building construct.

• Don't be lazy when naming variables – Don't use one letter variables, unless possibly the counters like i, j, and so on. There is no need, and only adds to the confusion to use n, l, and r instead of node, left and right.

• Naming methods is hard! – strangeCount() and isWantedNode() handles the count and test for the same thing, and should be named similarly, I think. Not sure if it's a better name, but the wanted nodes does one leaf node, and one none leaf node, so I used the leafNoLeaf in the code below.

Code refactored

The following code is untested, but you'll get the gist of the idea, I hope. I don't have a java compiler available currently.

class TreeNode {
    TreeNode left;
    TreeNode right;

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

/* Count all nodes having one leaf, and one non leaf node */
static int leafNoLeafCount(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return leafNoLeafCount(node.left) + leafNoLeafCount(node.right) +
           (isLeafNoLeafNode(node) ? 1 : 0);
}

/* Does this node exists, and have one internal and one external
   child node? */
static boolean isLeafNoLeafNode(TreeNode node) {
    if (node == null && node.right != null && node.left != null){
       return false;
    }
    boolean leftLeaf;
    boolean rightLeaf;

    // Not a big deal, but only check for leaf nodes once
    // once for any given node
    leftLeaf = isLeaf(node.left);
    rightLeaf = isLeaf(node.right);

    return (leftLeaf && !rightLeaf) || (!leftLeaf && rightLeaf);
}

/* Verify node exists, and has no child nodes */
public static boolean isLeaf(TreeNode node) {
    return node != null && node.left == null && node.right == null;
}

I'm not saying this code is optimal, but I think the comments are slightly better, and I've shaved off some methods. Lastly I removed the multiple calls to isLeaf() and isInternal() which was called 4 times in the original call, with 2 calls to isLeaf().

To me it is now a little easier to see what is actually happening, and it's a little more failsafe as the test for a null node is done in all methods, and there are no redundant methods.

Update: I was made aware that the isLeafNoLeaf() could allow a null to pass as an external node, which is not correct. Added a test at start to correct this behavior. This also triggers a question on what is correct behavior for isLeaf() when receiving a null node: Should it cast an exception if null, or silently ignore it and return false?

Answer 3

The other answers already gave a good solution to the question as you interpreted it. So I'm not going to repeat those.

Instead I'm going to see how much simpler things could be if you interpret the question a bit differently.

Nowhere in the question was there any mention of null beïng a valid child for a node. The question only speaks of internal and external nodes.

What happens if we think of an external node as a valid leaf node, and constrain an internal node to always contain 2 valid children, never null?

Let's start by defining 2 classes. An InternalNode and an ExternalNode. Now since an InternalNode has 2 children that could be either of those classes, let's also define a common superclass Node to be able to store the children properly. Since we're definately going to need to be able to see if a Node is a leaf node or not, let's make it easy for ourselves and also add a method isLeaf().

public abstract class Node {
    public abstract boolean isLeaf();
}

public class ExternalNode extends Node {
    public ExternalNode(){
    }

    @Override
    public boolean isLeaf() {
        return true;
    }
}

public class InternalNode extends Node {
    private Node left;
    private Node right;

    public InternalNode(Node left, Node right) {
        this.left = left;
        this.right = right;
    }

    public Node getLeft(){
        return left;
    }

    public Node getRight(){
        return right;
    }

    @Override
    public boolean isLeaf() {
        return false;
    }
}      

Now that we have our basic Node classes let's look at how to actually solve our problem. There are 2 possible ways to do this now. One is to write a method externally like you did. One thing to note here though, is that only InternalNode has getters for child nodes. So this requires casting:

public static int strangeCount(Node node){
    if(node.isLeaf()){
        return 0;
    }
    InternalNode internal = (InternalNode) node;
    return strangeCount(internal.getLeft()) +
            strangeCount(internal.getRight()) +
            (isWantedNode(internal)?1:0);
}

public static boolean isWantedNode(InternalNode node){
    //Did you know java has an xor operator for booleans?
    return node.getLeft().isLeaf() ^ node.getRight().isLeaf();
}

Alternatively we can also add a method to the Node classes to handle this cleaner (I'll only show the added methods for each class here):

public abstract class Node {
    public abstract int strangeCount();
}

public class ExternalNode extends Node {
    @Override
    public int strangeCount() {
        return 0;
    }
}

public class InternalNode extends Node {
    @Override
    public int strangeCount() {
        return strangeCount(getLeft()) +
                strangeCount(getRight()) +
                (isWantedNode()?1:0);
    }

    public boolean isWantedNode(){
        //Did you know java has an xor operator for booleans?
        return getLeft().isLeaf() ^ getRight().isLeaf();
    }
}   

Just a reminder: this entire answer only works if you do not allow null Nodes in the tree. It might not be applicable to how the actual question was intended to be solved. That's up to you to decide :)