Symmetric Binary Tree

Problem Overview

The problem "Symmetric Tree" (LeetCode Problem #101) involves checking whether a given binary tree is symmetric around its center. A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree. The problem can be understood in terms of verifying if two subtrees are reflections of each other.

URL: Symmetric Tree

Understanding the Problem

A symmetric tree is structurally identical when one subtree is a mirror reflection of the other. Consider the following tree:

    1
   / \
  2   2
 / \ / \
3  4 4  3

This tree is symmetric because the left and right subtrees are mirror images of each other. Conversely, a tree like:

    1
   / \
  2   2
   \   \
   3    3

Is not symmetric, since the structure and arrangement of nodes are not identical.

Key DSA Concepts and Theory

1. Binary Trees

A binary tree is a tree data structure in which each node has at most two children—referred to as the left child and the right child.

2. Recursion

Recursion is a method of solving a problem where a function calls itself as a subroutine. This allows problems to be solved in a simpler fashion and is critical when traversing or reflecting over a binary tree structure like in this problem.

3. Depth-First Search (DFS)

DFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root node and explores as far as possible along each branch before backtracking. In this problem, recursive DFS can be applied to compare nodes.

Solution Approach

The simplest approach to determine if a binary tree is symmetric is to perform a recursive check that verifies whether each pair of nodes are mirrors of each other. We need to compare the left and right subtree using a helper function.

Step-by-Step Solution

1. Edge Case: If the tree is empty (i.e., the root is null), it is inherently symmetric.

2. Recursive Helper Function:

   • Create a function isMirror(TreeNode left, TreeNode right) that checks for mirror symmetry.
   • Recursively check the condition for symmetry:
     • Both nodes must be null or both must be non-null and their values equal.
     • Recursively check if left.left is a mirror of right.right and left.right is a mirror of right.left.

3. Invocation:

   • Start the recursive process by calling isMirror(root.left, root.right).

Let's illustrate this with code implementations in C++ and Java.

C++ Code

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root == nullptr || isMirror(root->left, root->right);
    }

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

Java Code

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

    private 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);
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once in a depth-first manner, ensuring an efficient check.

• Space Complexity: O(h), where h is the height of the tree due to the recursion stack size in the worst case (a skewed tree).

Common Mistakes to Avoid

1. Null Checks: Ensure that both children nodes are checked for null before accessing their values or children.
2. Incorrect Base Conditions: Ensure that the base case correctly handles both null nodes as symmetric and any single null node as non-symmetric.

Similar Problems on LeetCode

1. Populating Next Right Pointers in Each Node - LeetCode #116
2. Binary Tree Level Order Traversal - LeetCode #102

Additional Resources and References

• Binary Tree Data Structure
• Recursion in Computer Science
• Depth-First Search Algorithm

This problem provides a good practice in understanding recursive tree traversal techniques to solve symmetry issues effectively. Understanding these concepts can also give insights into solving similar problems involving mirrored structures and DFS traversal.