Symmetric Tree - Leetcode Solution

Symmetric Tree is a problem on LeetCode that requires you to check whether a given binary tree is symmetric or not. A binary tree is symmetric if its left and right subtrees are mirror images of each other.

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

Output: true

Explanation: The above tree is symmetric.

Here's how you can solve this problem:

1. Base case: If the root node is null, then the tree is symmetric, and you can return True.

2. Check the left subtree and right subtree's values if they are equal. If the values are not equal, return False.

3. Recursively call the function to check whether the left subtree's left child and the right subtree's right child are symmetric, and the left subtree's right child and the right subtree's left child are symmetric.

4. If either of the subtrees is null, return False.

5. If the values of both subtrees are equal and their child subtrees are symmetric, return True.

6. Repeat steps 3-5 for each level of the tree until the entire tree is checked.

Here's the Python code to solve this problem using recursion:

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        return self.helper(root.left, root.right)
    
    def helper(self, left: TreeNode, right: TreeNode) -> bool:
        if left is None and right is None:
            return True
        if left is None or right is None or left.val != right.val:
            return False
        return self.helper(left.left, right.right) and self.helper(left.right, right.left)

In the above code, we first check if the root node is empty, and if it is, the function returns True. We then call the helper function, which takes the left and right subtrees as arguments.

The helper function returns True if both left and right subtrees are empty. If either of the subtrees is empty or they have different values, the function returns False.

If both subtrees have the same value, we make a recursive call to the function to check whether their child nodes are symmetric or not.

Let's see how this code works on the given example:

The input is:

[1,2,2,3,4,4,3]

The root node of the tree is 1.

We call the helper function:

self.helper(2, 2)

The left and right subtrees have the same value, so we call the helper function again:

self.helper(3, 3) and self.helper(4, 4)

Both left and right subtrees have the same value, and their child nodes are both empty, so we return True.

We repeat the above process until all nodes have been checked.

The final output is True, indicating that the input tree is symmetric.

1