Test if two BSTs are equal in Java

Question

I would like to test if two given BSTs (Binary Search Trees) are equal in Java. The BST nodes do not have pointers to the parent nodes.

The simplest solution is to traverse both BSTs, create two traversal lists and test if the lists are equal. However it requires O(N) memory.

I would like to try another way: create an Iterator, which traverses the BSTs, and ... the rest is obvious.

Does it make sense? Is there any "better" (simpler and efficient) solution to test if two BSTs are equal?

Answer 1

1. Binary search tree is a tree, right?

2. Two trees are equal if they have the same root and the same children.

3. Each child is also a tree.

4. See point 2.

Hint: recursion. The memory consumption is O(logn) (prove it yourself).

Answer 2

Implement a recursive equals() method. It would require no memory, and would be easy to code.

Something like this should work:

public class Node {

    Object value;
    private Node left;
    private Node right;

    public boolean equals(Object o) {
        if (o instanceof Node) {
            Node node = (Node)o;
            if (value.equals(node.value)) {
                return true;
            }
            return ((left == null && node.left == null) || left.equals( node.left)) && 
                    ((right == null && node.right == null) || right.equals( node.right));
        }
        return false;
    }
}

Note that you should override hashCode() to reflect this implementation, so consider naming the above impl as equalsDeep() instead and skipping the hashCode() impl.