🌳 How Python Recursively Compares Binary Trees Using __eq__

---

When working with binary trees in Python, comparing two trees for equality is a common task—whether for testing, validation, or logic flow. You might expect that comparing trees is simple, but the magic lies in how Python uses recursion and short-circuit logic to perform this task efficiently.

In this post, we’ll uncover how a binary tree class uses the special __eq__ method to recursively compare itself with another tree—left first, then right.

---

✨ The __eq__ Method in Python

In Python, when you use the == operator between two objects, it internally calls the __eq__ method defined in the class of those objects.

Here’s how it might look in a custom binary tree Node class:

class Node:
    def __init__(self, value, left_child=None, right_child=None):
        self.value = value
        self.left = left_child
        self.right = right_child

    def __eq__(self, tree):
        return (self.value == tree.value and
                self.left == tree.left and
                self.right == tree.right)

This method compares:

• The value of the current nodes,
• The left child nodes (recursively),
• The right child nodes (recursively).

---

🔁 How the Recursion Works

Let’s say you have two trees like this:

a = Node(5, Node(3), Node(7))
b = Node(5, Node(3), Node(7))
print(a == b)  # True

Step-by-Step Evaluation:

1. Compare root values: 5 == 5 ✅
2. Recursively compare left subtrees: Node(3) == Node(3) ✅
   • 3 == 3 ✅
   • Left and right are both None ✅
3. Recursively compare right subtrees: Node(7) == Node(7) ✅
   • 7 == 7 ✅
   • Left and right are both None ✅

✅ Result: The trees are identical.

---

⚠️ Left First, Then Right — Not Simultaneous

Python uses short-circuit logic with the and operator. This means:

return (self.value == tree.value and
        self.left == tree.left and
        self.right == tree.right)

Evaluates in this order:

1. self.value == tree.value
2. self.left == tree.left (recursive call)
3. self.right == tree.right (recursive call)

Python stops evaluating as soon as any condition fails.

For example:

a = Node(5, Node(3), Node(7))
b = Node(5, Node(4), Node(7))
print(a == b)  # False

Here, Node(3) != Node(4), so Python never even compares the right child.

---

📊 Visual Diagram of Comparison

Compare:      [5] == [5]
                |
     -------------------------
    |                         |
[3] == [3]              [7] == [7]
    |                         |
[None]==[None]        [None]==[None]
[None]==[None]        [None]==[None]

---

🧠 Summary

• The __eq__ method recursively checks whether two binary trees are equal.
• Python evaluates conditions left to right, with left subtree checked first.
• The use of and ensures short-circuiting—it skips unnecessary comparisons.
• This is a depth-first approach to tree equality.

---

🧪 Practice Challenge

Try writing your own tree comparison method without using ==, and test whether you understand the flow. Use small trees, draw them on paper, and trace the recursion manually. You’ll gain powerful insight into both recursion and Python’s evaluation model.

---