Solution For Symmetric Tree

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.

Step by Step Implementation For Symmetric Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return isMirror(root.left, root.right);
    }
    
    public boolean isMirror(TreeNode left, TreeNode right){
        if(left==null && right==null) return true;
        if(left==null || right==null) return false;
        return (left.val==right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

def isSymmetric(root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    # If the tree is empty, it is automatically symmetric
    if not root:
        return True
    
    # Check if tree is symmetric by comparing the left and right subtrees
    return checkSymmetry(root.left, root.right)
    
def checkSymmetry(leftSubtree, rightSubtree):
    # If both subtrees are empty, they are symmetric
    if not leftSubtree and not rightSubtree:
        return True
    # If one subtree is empty and the other is not, the tree is not symmetric
    elif not leftSubtree or not rightSubtree:
        return False
    # If the root values of the subtrees are not equal, the tree is not symmetric
    elif leftSubtree.val != rightSubtree.val:
        return False
    # If we reach this point, we know that the root values are equal and that 
    # we have two non-empty subtrees. We check the symmetry of the subtrees by 
    # comparing the left child of the left subtree with the right child of the 
    # right subtree and vice versa.
    else:
        return checkSymmetry(leftSubtree.left, rightSubtree.right) and \
               checkSymmetry(leftSubtree.right, rightSubtree.left)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    // base case - if tree is empty, it is symmetric
    if (!root) {
        return true;
    }
    
    // recursive function to check if tree is symmetric
    function checkSymmetric(node1, node2) {
        // if both nodes are null, they are symmetric
        if (!node1 && !node2) {
            return true;
        }
        // if only one node is null, the tree is not symmetric
        if (!node1 || !node2) {
            return false;
        }
        // if values of nodes are not equal, the tree is not symmetric
        if (node1.val !== node2.val) {
            return false;
        }
        // check left subtree of node1 is equal to right subtree of node2 and vice versa
        return checkSymmetric(node1.left, node2.right) && checkSymmetric(node1.right, node2.left);
    }
    
    return checkSymmetric(root.left, root.right);
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isMirror(root->left, root->right);
    }
    
    bool isMirror(TreeNode* t1, TreeNode* t2){
        if(!t1 && !t2) return true;
        if(!t1 || !t2) return false;
        return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSymmetric(TreeNode root) {
        // Base case: 
        if (root == null) {
            return true;
        }
        
        // Recursive case: 
        return IsSymmetricHelper(root.left, root.right);
    }
    
    public bool IsSymmetricHelper(TreeNode left, TreeNode right) {
        // Base case: 
        if (left == null || right == null) {
            return left == right;
        }
        
        // Recursive case: 
        if (left.val != right.val) {
            return false;
        }
        
        return IsSymmetricHelper(left.left, right.right) && IsSymmetricHelper(left.right, right.left);
    }
}