
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;

        Queue queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);

        while (!queue.isEmpty()) {
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();

            if (leftNode == null && rightNode == null)
                continue;
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val)
                return false;

            queue.add(leftNode.left);
            queue.add(rightNode.right);
            queue.add(leftNode.right);
            queue.add(rightNode.left);
        }

        return true;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Recursive(DFS) Approach 2:


class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null)
            return true;
        if (leftNode == null || rightNode == null || leftNode.val != rightNode.val)
            return false;

        return isMirror(leftNode.left, rightNode.right) && isMirror(leftNode.right, rightNode.left);
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The "Symmetric Tree" problem involves determining if a binary tree is symmetric around its center. A binary tree is symmetric if the left and right subtrees are mirror images of each other.

This problem is a common one in tree algorithms, as it checks for a balanced or symmetrical structure. It is often useful in validating the structure of data represented as a tree.

Problem Statement

Given the root of a binary tree, return true if it is symmetric, or false if it is not. A tree is symmetric if the left and right subtrees are mirror images of each other.

The tree is represented by the TreeNode class. You need to implement a function to determine if the tree is symmetric.

Approach

To solve this problem, we can use a recursive approach to compare the left and right subtrees of the tree. A tree is symmetric if the following conditions hold:

The left subtree and the right subtree are mirror images of each other.
The left child of the left subtree is equal to the right child of the right subtree.
The right child of the left subtree is equal to the left child of the right subtree.

The main idea is to compare the left and right subtrees for symmetry by checking their root values and recursively comparing their children. If at any point the values don't match, the tree is not symmetric.

We will use a helper function to check if two subtrees are mirror images of each other. This function will compare the nodes and recursively check the left and right children.

Algorithm

The algorithm can be described as follows:

If the tree is empty (root is null), return true because an empty tree is trivially symmetric.
Recursively check if the left and right subtrees are mirror images by comparing the root values and their children.
If the values match and the left child of the left subtree matches the right child of the right subtree (and vice versa), the tree is symmetric.
If at any step the values do not match or the children are not mirror images, return false.

The recursive function will return true if the tree is symmetric and false otherwise.

Example

Consider the following binary tree:

This tree is symmetric because the left and right subtrees are mirror images of each other. The left child of the left subtree (3) matches the right child of the right subtree (3), and similarly, the right child of the left subtree (4) matches the left child of the right subtree (4).

Now consider this tree:

This tree is not symmetric because the left subtree has a right child (3) but the right subtree does not have a left child.

Code Implementation

Below is the Python code to check if a binary tree is symmetric:

In this code: - We define a helper function `isMirror(t1, t2)` to recursively check if two trees are mirror images of each other. - We start by comparing the left and right subtrees of the root. - If the root is null, we return true since an empty tree is symmetric. - We then check if the values of the nodes are the same and recursively check their left and right children for symmetry.

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node once while checking for symmetry.

The space complexity is O(h), where h is the height of the tree, due to the recursion stack used by the recursive calls. In the worst case, for a skewed tree, the height will be O(n), resulting in a space complexity of O(n). For a balanced tree, the height will be O(log n), resulting in a space complexity of O(log n).

Optimized Approach

The current approach is already optimal in terms of time complexity, as we must check each node once to ensure the tree is symmetric. The space complexity could be reduced by using an iterative approach with a queue, but the time complexity will still remain O(n).

The recursive DFS approach is both simple and effective for this problem, and the current space complexity is manageable for most tree sizes.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the binary tree. The space complexity is O(h), where h is the height of the tree due to the recursion stack. In the worst case, for an unbalanced tree, the height will be O(n), resulting in a space complexity of O(n). For a balanced tree, the height will be O(log n), so the space complexity will be O(log n).

Conclusion

The "Symmetric Tree" problem involves determining if a binary tree is symmetric around its center. By using a recursive approach to compare the left and right subtrees, we can easily check if the tree is symmetric. The time complexity of this solution is O(n), and the space complexity is O(h), where n is the number of nodes in the tree and h is the height of the tree.