CODEWITHSUNDEEP
javabinary-search-tree
lsund
lsund

Reputation: 744

Test if two binary search trees has the same set of elements?

I am just starting out with java and recursive methods and i need some help: I need to determine if two Binary Search Trees has exactly the same set of elements, regardless of the structure of the tree.

I have written a method that checks if the the tree contains an element and its called contains()

this is what i got so far:

    public boolean sameContents(Node n2) {

    if (contains(n2, n2.key) && n2.left == null && n2.right == null) { return true; }
    if (contains(n2, n2.key) && n2.left != null) { sameContents(n2.left); }
    if (contains(n2, n2.key) && n2.right != null) { sameContents(n2.right); }
     return false; 
   }

Basicly my idea is that the method is running as long as a node still has a child, and if the trees match. I call the method with for example testTree1.sameContents(testTree2); but the method always returns false... Can someone point out how this should be done?

Upvotes: 0

Views: 2846

Answers (3)

Vladimir Kostyukov
Vladimir Kostyukov

Reputation: 2552

There is another way to do that. You can convert your trees into string representations, using pre-order traversal or in-order traversal. It will take O(n) time. Than you can check whether these strings equal or not. It can be done in O(n) time too. So, the total running time is O(n).

This method looks similar to the solution with iterators but this one is more generic, since can be used for 'is-subtree' task (chechs wether tree t1 is subtree of t2). In this case use can use isSubstring() method instead of equals(). If tree t1 is subtree of t2 than t1's string representaion is substring of t2's. The isSubstring() can be done in O(log n) time.

Upvotes: 1

GJ13
GJ13

Reputation: 488

Can you do a inorder traversal on both trees and check if the result of both the traversals are same. If same, could we assume that both trees have the same set of elements.

Upvotes: 0

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

The best way to do this is with an Iterator object - if two binary search trees contain the same elements then their iterators' next methods should return the same values (even if their structures are different).

// returns true if the trees are equivalent, else false
Iterator itr1 = tree1.getIterator();
Iterator itr2 = tree2.getIterator();
while(itr1.hasNext() && itr2.hasNext()) {
    if(!itr1.next().equals(itr2.next())) {
        return false;
    }
}
return !itr1.hasNext() && !itr2.hasNext(); // returns true if trees were the same size, else false

You ought to already have an inorder binary tree traversal method, so you've already got an Iterator - just add an ArrayList/Stack to take the place of the call stack so that you can pause the traversal (whenever you would be making a recursive method call, store the current node to your Stack)

Upvotes: 1

Related Questions