CODEWITHSUNDEEP
javaalgorithmbinary-tree
Dustin
Dustin

Reputation: 3

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.

Upvotes: 0

Views: 62

Answers (2)

ruakh
ruakh

Reputation: 183270

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.)

Upvotes: 1

eavidan
eavidan

Reputation: 5564

You should replace

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;

With 

return root.data == target && allEqual(root.left, target) && allEqual(root.right, target);

Since your current code ignores the right subtree (and also, the null checks are redundant because you check each time if the root is null)

As for avoiding recursion, you could use a different while loop, pushing the children of the current node into a stack (initialized with the root) and always popping the first element. (Of course, while data == target)

Upvotes: 0

Related Questions