Checking if a Binary Tree is Symmetric : Leetcode Solution.

Introduction

Symmetry in binary trees is a common topic in computer science. A tree is symmetric if the left and right subtrees are mirror images of each other. This article explains how to check if a binary tree is symmetric using recursion in Python.

---

Problem Statement

Given the root of a binary tree, determine whether it is symmetric around its center.

Example

Input:

    1
   / \
  2   2
 / \ / \
3  4 4  3

Output:

True

Explanation:

• The left and right subtrees are mirror images of each other.

Counterexample: Input:

    1
   / \
  2   2
   \    \
   3     3

Output:

False

Explanation:

• The structure of the left and right subtrees is not symmetric.

---

Approach

The solution uses a recursive depth-first search (DFS) approach to traverse both subtrees simultaneously, comparing nodes for symmetry.

Steps:

1. Base Case:

   • If both left and right are None, return True (empty subtrees are symmetric).

   • If one of left or right is None, return False (asymmetric structure).

2. Recursive Case:

   • Check if left.val equals right.val.

   • Recursively compare:

     • left.left with right.right (outer symmetry).

     • left.right with right.left (inner symmetry).

3. Return Final Result:

   • Use the recursive helper function dfs to determine symmetry.

---

Complexity

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

  • Each node is visited exactly once, where $$n$$ is the total number of nodes in the tree.

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

  • The recursion stack depth depends on the height of the tree, where $$h$$ is the height of the tree.

---

Python Code

Here 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 isSymmetric(self, root):
        def dfs(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False

            return (left.val == right.val and
                    dfs(left.left, right.right) and
                    dfs(left.right, right.left))

        if not root:
            return True

        return dfs(root.left, root.right)

---

Example Walkthrough:

Let’s walk through the algorithm with an example:

Input Tree:

    1
   / \
  2   2
 / \ / \
3  4 4  3

Steps:

1. Compare root.left and root.right (values 2 and 2): Values match.

2. Recursively check:

   • root.left.left (3) with root.right.right (3): Values match.

   • root.left.right (4) with root.right.left (4): Values match.

3. All recursive checks pass. The tree is symmetric.

Output:

True

---

Advantages of Recursion in Symmetry Checks

1. Clarity: The recursive approach mirrors the structure of the binary tree, making the code intuitive.

2. Efficiency: Only necessary nodes are visited, optimizing runtime.

---

Conclusion

This recursive solution efficiently checks if a binary tree is symmetric. For large trees, ensure the recursion depth does not exceed system limits to prevent stack overflow. Iterative approaches can also be considered for such cases.

If you found this article helpful, feel free to explore more binary tree problems and techniques!

---

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