Dustin Dustin - 2 months ago 6
Java Question

Verifying all data entries in a binary tree are equal

I'm using Java for a Binary Tree (not a Binary Search Tree). I have the class and instance variable declarations:

class intBTNode
{
private int data;
private intBTNode left;
private intBTNode right;


What I want to do is write a method which returns true only if all of the entries in the tree are equal to a target number or if the tree is empty.
I wrote the following code:

public static boolean allEqual(intBTNode root, int target)
{
if (root == null)
return true;
if (root.data == target && root.left != null)
return allEqual(root.left, target);
if (root.data == target && root.right != null)
return allEqual(root.right, target);
return false;
}


I'm trying to work my way through this to check the code, but I am not sure I am adequately checking all of the nodes (i.e. the leaf). Also, I am trying to work out a way to attack this problem that is not recursive or would be more efficient. Any help or suggestions would be appreciated.

Answer

You are not adequately checking all nodes.

The problem is that if root.left is non-null, then you never examine root.right; so a tree like this:

     3
    / \
   3   4

will be mis-classified as containing only the target.

A better approach is to write:

public static boolean allEqual(intBTNode root, int target)
{
    return root == null
        || root.data == target
           && allEqual(root.left, target)
           && allEqual(root.right, target);
}

If you want to avoid recursion for some reason, you can do that by maintaining a collection of nodes that you've "discovered" (by visiting their parent) but haven't yet actually "visited" (by examining their data and children), and continually pulling nodes out of that collection, and visiting them, until it's empty:

public static boolean allEqual(intBTNode root, int target)
{
    List<intBTNode> nodesToVisit = new ArrayList<intBTNode>();
    nodesToVisit.add(root);
    while (! nodesToVisit.isEmpty()) {
        intBTNode node = nodesToVisit.remove(nodesToVisit.size() - 1);
        if (node == null)
            continue;
        if (node.data != target)
            return false;
        nodesToVisit.add(node.left);
        nodesToVisit.add(node.right);
    }
    return true;
}

(This is actually exactly equivalent to the recursive version, just using an ArrayList as a stack instead of using the call stack.)