Checking if 2 Binary search trees are equal

Question

I'm creating a binary search tree project, and one of the questions is to create 2 trees and check if they're equal or not. When I implement the method, I keep getting firstTree and secondTree are equal. Here's the relevant code:

BstTest2 firstTree = new BstTest2();
firstTree.addNode(50, "Francisco Domingo Carlos Andres Sebastián d'Anconia");
firstTree.addNode(25, "John Galt");
firstTree.addNode(15, "Hugh Akston");
firstTree.addNode(30, "Ragnar Danneskjöld");
firstTree.addNode(85, "Hank Reardan"); //implementing add method

BstTest2 secondTree = new BstTest2();
secondTree.addNode(50, "Francisco Domingo Carlos Andres Sebastián d'Anconia");
secondTree.addNode(25, "John Galt");
secondTree.addNode(15, "Hugh Akston");
secondTree.addNode(30, "Ragnar Danneskjöld");
secondTree.addNode(75, "Midas Mulligan");
secondTree.addNode(85, "Hank Reardan");

if(firstTree.isEqual(secondTree))
{
     System.out.println("firstTree and secondTree are equal");
}
else
{
     System.out.println("firstTree and secondTree are not equal");
}

isEqual and check methods for comparing the trees

public boolean isEqual(BstTest2 tree1)
{
    return check(this.rootNode, tree1.rootNode);
}
public boolean check(Node node1, Node node2)
{
    if((node1 == null) && (node2 == null))
    {
        return true;
    } 
    else if((node1 == null) || node2 != null)
    {
        return false;
    } 
    else if((node1 != null) || node2 == null)
    {
        return false;
    } 
    else
    {
        return check(node1.leftChild, node2.leftChild) && check(node1.rightChild, node2.rightChild);
    }
}

What did I do wrong in my isEqual() and check() methods that I keep getting " firstTree and secondTree are equal" when the trees are not equal?

you don't check if the contents of the nodes are equal, but just if the nodes are null or not null — MarcoLucidi
– MarcoLucidi, Commented Jul 26, 2020 at 9:21

Ynjxsjmh · Accepted Answer · 2020-07-26 09:46:40Z

1

You forget to check if the value of node1 and node2 are the same.

If they are not the same, it means these two trees are not same.
If they are the same, we keep on checking if their left and right child are the same.


public boolean check(Node node1, Node node2)
{
    if((node1 == null) && (node2 == null))
    {
        return true;
    } 

    // If only one node is null, it means these two trees are not the same
    // These two nodes here couldn't both be null because we check this condition earlier.
    if(node1 == null || node2 == null)
    {
        return false;
    } 

    // Check if the value of node1 and node2 are the same
    if(node1.val != node2.val)
    {
        return false;
    } 

    return check(node1.leftChild, node2.leftChild) && check(node1.rightChild, node2.rightChild);
}

answered Jul 26, 2020 at 9:46

Ynjxsjmh

30.3k7 gold badges43 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Arjun Singh Over a year ago

Thank you! I had a feeling I made a really stupid error lol

Collectives™ on Stack Overflow

Checking if 2 Binary search trees are equal

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related