Binary Tree: Method to return TRUE if all values equal a specific value

Question

In Java, I'm working on coding a boolean method that traverses through an entire binary tree for a specific value (e.g. integer value 1) and if all the nodes are that value, the method returns true.

So far, I have the following:

public static boolean everything1(IntBTNode root) {
    if (root.data == 1) { 
        everything1(root.left);
        return true;
        everything1(root.right);
    }
}

Am I on the right track?

Answer 1

First of all, every line of code after a return statement will never be executed. So careful there. Second, if you are going to do it with recursion, I recommend the next:

public static boolean everything1(IntBTNode root) {
    if (root == null) {
        return true;
    } else {
        return (root.data == 1) && everything1(node.left) && everything1(root.right)
    }
}

1. check if the root (node) is null, if it is, just return true.
2. else, check if the root data is 1, short circuited with && because if you get false the execution finish there, and you want to check if all the items are 1
3. check recursively if the value is in the left node
4. check recursively if the value is in the right node

Answer 2

The logic of your recursive method needs to reflect the way you think, in your native language, of the action the method performs. In your case, everything in a tree is 1 when all of the following conditions are true:

• Node itself is 1, and
• Everything on the left is 1, and
• Everything on the right is 1

It is also trivially true when the node itself is null, which is your base case.

When you start implementing your recursive method, imagine that it is already available for your use. Hence, the code could be written as follows:

public static boolean everything1(IntBTNode node) {
    return (node == null)
        || (node.data == 1 && everything1(node.left) && everything1(root.right));
}

Recursive calls to everything1 correspond to lines 2 and 3 of the description above.

Answer 3

but before you call ·everything1·, i think you should determine IntBTNode node is null or not.

public static boolean everything1(IntBTNode node, int key) {
    if(node == null) return true;
    if(node.data != key){
        return false;
    }
    return everything1(node.left, key) && everything1(node.right, key);
}