The Symmetric Tree problem asks us to check whether a given binary tree is a mirror image of itself around its center.

In simple terms:

• A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
• For every node, the left child of one subtree must match the right child of the other subtree, and vice versa.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: [1,2,2,3,4,4,3]

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

Output: True
Explanation: The tree is symmetric.

Example 2

Input: [1,2,2,null,3,null,3]

        1
       / \
      2   2
       \   \
        3   3

Output: False
Explanation: The tree is not symmetric.

Intuition

To determine whether a tree is symmetric:

• Compare the left subtree and the right subtree.
• At every step:
  • If both nodes are None → symmetric so far.
  • If only one is None → not symmetric.
  • If values differ → not symmetric.
  • Otherwise, recursively check:
    • Left child of node1 with Right child of node2.
    • Right child of node1 with Left child of node2.

This recursive mirroring ensures symmetry validation.

Solution: Recursive DFS

Code Implementation

class Solution:
    def solve(self, node1, node2):
        if node1 is None or node2 is None:
            return node1 == node2
        if node1.val != node2.val:
            return False

        # Compare left of one with right of the other
        leftSide = self.solve(node1.left, node2.right)
        if leftSide == False:
            return False

        # Compare right of one with left of the other
        rightSide = self.solve(node1.right, node2.left)
        if rightSide == False:
            return False

        return leftSide and rightSide

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.solve(root.left, root.right)

Code Explanation

• solve(node1, node2):
  • Compares two nodes recursively.
  • Handles base cases where nodes are None.
  • Checks value equality.
  • Recursively compares opposite children:
    • node1.left with node2.right.
    • node1.right with node2.left.
• isSymmetric(root):
  • Starts the recursion by comparing the left and right children of the root.

Dry Run

Input: [1,2,2,3,4,4,3]

1. Start: solve(root.left=2, root.right=2) → values match.
2. Compare: solve(2.left=3, 2.right=3) → values match.
3. Compare: solve(3.left=None, 3.right=None) → symmetric.
4. Compare: solve(2.right=4, 2.left=4) → values match.
5. Continue until all recursive checks succeed.

Final Result = True.

Time and Space Complexity

• Time Complexity: O(N)
  • Each node is visited once.
• Space Complexity: O(H)
  • Due to recursion stack, where H = height of the tree.
  • In worst case (skewed tree), space = O(N).
  • In balanced tree, space = O(log N).

Conclusion

The Symmetric Tree problem can be solved efficiently using recursive DFS.

• At every step, we compare the left subtree of one side with the right subtree of the other.
• If all corresponding nodes match, the tree is symmetric.

This approach is clean, recursive, and efficient, running in O(N) time with O(H) space.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.