How to Compare Two Binary Trees in Python

How Is Our Tree?

our tree is something like this:

for simplicity we skipped the definition of insert method, but we will provide the full code at the end, for now lets focus on the title

What Are We Going to Do?

we are goint to make a method named equal which checks if those two binary trees are equal or not, we want to use it like this:

first we define a tree with three nodes

then we create another tree with the exact same nodes

now we call our magic equal method to check the equality

and the result will of course be True

Lets Do The Magic:

first we define a method named equal which is going to be exposed outside this method has two inputs the famous self and the other, first one as you know refers to the object and the other is going to refer to the second tree

inside of this method we are calling a private static method named __equal.

the __ at the begining makes this private and the fact that we are calling __equal with the calss name not the objects name makes it a static method.

this is where the actual logic happens, this static method is the one we called in the equal method earlier, this method gets two inputs named self_root and other_root which like the names implies they are the root node of the two trees

in the first scenario both nodes are None and the result will be True in this situation.

in the second scenario neither of them is None, for this we use a pre-order traversal and first check the value of the roots and then check the values of left and right sub-trees and create a boolean experssion to return.

at the end we return False, we get here if one of our nodes is None and the other one is not, so the result is False under this circumstance.

an Edge Case:

what if we pass None to our equal Method?

in this case we will face a beautifull AttributeError

caused by this line:

in order to fix this we have to add a condition to our equal method like this:

The Full Code:

hope it was useful guys, to see the full code, click here