Symmetric Tree - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Determine if a binary tree is symmetric, i.e., its left and right subtrees are mirror images.
Define a helper function same(root1, root2) to check if two subtrees are mirror images:
If both root1 and root2 are None, return True.
If exactly one of root1 or root2 is None, return False.
If root1.val does not equal root2.val, return False.
Recursively check if root1.left is a mirror of root2.right and root1.right is a mirror of root2.left.
Call same(root, root) to check if the tree is symmetric with itself.
Return the result of the same function.

Code Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def same(root1, root2):
            if not root1 and not root2:
                return True

            if not root1 or not root2:
                return False
            
            if root1.val != root2.val:
                return False
            
            return same(root1.left, root2.right) and \
                   same(root1.right, root2.left)

        return same(root, root)
        # Time: O(n)
        # Space: O(height) or O(n)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isMirror(root, root);
    }

private:
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        if (t1->val != t2->val) return false;
        
        return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
    }
};

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}

var isSymmetric = function(root) {
    function isMirror(t1, t2) {
        if (t1 === null && t2 === null) return true;
        if (t1 === null || t2 === null) return false;
        if (t1.val !== t2.val) return false;
        
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    return isMirror(root, root);
};

Detailed Explanation

Get Personalized Support at AlgoMap Bootcamp 💡