CODEWITHSUNDEEP
javaequalitybinary-search-tree
Michael
Michael

Reputation: 42050

Test if two BSTs are equal in Java

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?

Upvotes: 4

Views: 1900

Answers (3)

TeaCupApp
TeaCupApp

Reputation: 11452

The easiest way could be, create a hash of both tree and then check whether they are equal or not. This only apply if the content of both tree are same as well.

How to create checksum and then compare those checksum.

http://www.mkyong.com/java/how-to-generate-a-file-checksum-value-in-java/

Upvotes: 1

Bohemian
Bohemian

Reputation: 424993

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.

Upvotes: 1

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 340723

  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: . The memory consumption is O(logn) (prove it yourself).

Upvotes: 7

Related Questions