Comparing Two Binary Trees for Equality : Leetcode Solution.

Introduction

Binary trees are a fundamental data structure in computer science. One common problem is determining whether two binary trees are identical. Identical trees have the same structure and node values. This article discusses a Python solution to check if two binary trees are the same using recursion.

---

Problem Statement

Given the roots of two binary trees p and q, return True if the two trees are structurally identical and have the same node values, otherwise return False.

Example

Input: Tree 1:

    1
   / \
  2   3

Tree 2:

    1
   / \
  2   3

Output:

True

Explanation:

Both trees have the same structure and identical values at every corresponding node.

---

Approach

The solution uses recursion to traverse both trees simultaneously and compare their structures and node values.

Steps:

1. Base Case:

   • If both nodes are None, return True as two empty trees are identical.

   • If only one of the nodes is None or the values of the nodes are different, return False.

2. Recursive Check:

   • Recursively compare the left subtrees of both nodes.

   • Recursively compare the right subtrees of both nodes.

   • If both subtrees are identical, return True. Otherwise, return False.

---

Complexity

• Time Complexity: $$O(n)$$

  • Every node in both trees is visited once, where $$n$$ is the total number of nodes in the smaller tree.

• Space Complexity: $$O(h)$$

  • The recursion stack space depends on the height of the trees, where $$h$$ is the height of the trees.

---

Python Code

Below is the Python implementation of the solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False

        return (self.isSameTree(p.left, q.left) and
                self.isSameTree(p.right, q.right))

---

Example Walkthrough

Let’s walk through the algorithm with an example:

Input Trees: Tree 1:

    1
   / \
  2   3

Tree 2:

    1
   / \
  2   3

Steps:

1. Start at the root nodes (1 for both trees). Values are the same, proceed.

2. Recursively check the left children:

   • Both are 2. Values match, so proceed to their children (both None).

3. Recursively check the right children:

   • Both are 3. Values match, so proceed to their children (both None).

4. All checks pass, return True.

Output:

True

---

Advantages of Recursion in Tree Comparison

1. Simplicity: Recursive solutions naturally reflect the structure of binary trees.

2. Clarity: Each recursive call handles a smaller part of the tree, making the logic straightforward.

---

Conclusion

The recursive approach to checking tree equality is efficient and elegant. It ensures all nodes are compared in both structure and value. This solution can be extended to solve similar tree-based problems, such as subtree matching or mirror tree checks.

If you enjoyed this article, feel free to explore more tree-related algorithms or share your thoughts!

---

Let’s Connect! If you found this article helpful, feel free to connect with me on LinkedIn and check out more of my articles on Hashnode!