Symmetric Tree (Leet Code-101)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 101. This is a Leet code problem named Symmetric Tree. We will solve it using python and it is the best space and time-optimized solution.

Question of Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Each node in a binary tree has a left subtree and a right subtree. An empty subtree, a single node, or another binary tree can all be subtrees. If the left subtree of the root node mirrors the right subtree, a binary tree is said to be symmetric. The binary tree in the first example is symmetric.

Example

Example 1

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Approach to solve Symmetric Tree

To solve this problem we will recursively call the left and right subtree and check whether they are mirror images of each other or not. If they are mirror images then we recursively call the function till we find none otherwise we return false.

Algorithm

This method performs the following steps for a given input binary search tree:

Create an inner function to compare sides. We pass the left and the right node at a time to compare.
Check base case if both left and right nodes are none then return true.
If the left and right nodes exist and both nodes’ values are equal, do step 4.
Call the compare side function twice and return and condition for them. The two parameters to call are, first, with left child of left node and right child of a right node, second left child of right node and right child of the left node.
If any of the above conditions are false return False.
end if
End inner function

Python Code for Symmetric Tree

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    
        #inner function
        def compareSides( left, right):
            #base case
            if left is None and right is None:
                return True
            #if left and right both value exists and equal
            elif left and right and (left.val == right.val) :
                # recursively call compareSides function for left and right side
                return   compareSides(left.left, right.right) and compareSides(left.right, right.left)
                 
            # otherwise return false
            else:
                return False           
    
        return compareSides(root.left, root.right)