Symmetric Tree easy

Problem Statement

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

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

Steps

  1. Recursive Approach: We'll use a recursive helper function to compare subtrees. The core idea is that a tree is symmetric if the left subtree is a mirror of the right subtree.

  2. Base Cases:

    • If both nodes are nullptr, they are symmetric (empty subtrees).
    • If one is nullptr and the other isn't, they are not symmetric.
    • If their values are different, they are not symmetric.

  3. Recursive Step: If the base cases pass, we recursively check if the left subtree of the left node is symmetric to the right subtree of the right node, and vice-versa.

Explanation

The symmetry check boils down to comparing nodes at the same level but on opposite sides of the tree. The recursion elegantly handles this level-by-level comparison. The base cases ensure that we correctly handle the situations where subtrees might be empty or have different values.

Code

/**
 * 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 == nullptr) return true; // Empty tree is symmetric
        return isMirror(root->left, root->right);
    }

    bool isMirror(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) return true; // Base case: both null
        if (left == nullptr || right == nullptr) return false; // Base case: one null, other not
        if (left->val != right->val) return false; // Base case: values differ

        // Recursive step: check if left subtree of left is mirror of right subtree of right, and vice versa
        return isMirror(left->left, right->right) && isMirror(left->right, right->left);
    }
};

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at most once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is logâ‚‚(N).