Dustin - 8 months ago 49

Java Question

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