NUHMAN.com

Introduction

LeetCode 101: Symmetric Tree is a problem where you are asked to determine if a binary tree is symmetric around its center. A tree is symmetric if its left and right subtrees are mirror images of each other.

In this problem, you will implement an algorithm that checks whether a binary tree is symmetric.

Problem Statement

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

Example:

go

Input:
    Tree 1:
        [1, 2, 2, 3, 4, 4, 3]
Output: true
Explanation: The tree is symmetric.

Input:
    Tree 2:
        [1, 2, 2, null, 3, null, 3]
Output: false
Explanation: The tree is not symmetric.

Input:
    Tree 3:
        [1, 2, 2, 3, 4, 4, 3]
Output: true
Explanation: The tree is symmetric around its center.

Approach:

Recursive Approach

To determine if a binary tree is symmetric, we can recursively check the following:

1. The root node must be symmetric with itself.
2. The left and right subtrees of the root node must be mirror images of each other.

Steps:

1. Base Case: If both trees are nil, they are symmetric.
2. Mirror Condition: The left subtree of the left node should be a mirror of the right subtree of the right node, and vice versa.
3. Recursion: Recursively compare the left subtree with the right subtree in reverse order.

Go Implementation

Recursive Solution

go

package main

// TreeNode represents the structure of a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// isSymmetric checks if a binary tree is symmetric.
func isSymmetric(root *TreeNode) bool {
    // If the root is nil, the tree is symmetric by default.
    if root == nil {
        return true
    }
    
    // Recursively check if the left and right subtrees are mirror images.
    return isMirror(root.Left, root.Right)
}

// isMirror checks if two trees are mirror images of each other.
func isMirror(t1 *TreeNode, t2 *TreeNode) bool {
    // If both nodes are nil, the trees are symmetric.
    if t1 == nil && t2 == nil {
        return true
    }
    
    // If one node is nil and the other is not, they are not symmetric.
    if t1 == nil || t2 == nil {
        return false
    }
    
    // Check if the values are equal and the subtrees are mirror images.
    return t1.Val == t2.Val && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}

Explanation:

1. TreeNode Structure:

• The TreeNode structure represents a binary tree node with three fields: Val (the value of the node), Left (pointer to the left child), and Right (pointer to the right child).

1. isSymmetric Function:

• This function checks if a binary tree is symmetric by calling the helper function isMirror with the left and right children of the root.

1. isMirror Function:

• This function is a recursive helper function that checks whether two subtrees are mirror images of each other.
• It performs the following checks:
• If both nodes are nil, they are symmetric.
• If one node is nil and the other is not, they are not symmetric.
• If the values of the nodes are equal, it recursively checks if the left subtree of one node is a mirror of the right subtree of the other node, and vice versa.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the binary tree.

Time Complexity:

• We visit each node in the tree exactly once, so the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

• The space complexity is determined by the recursion stack. In the worst case (a skewed tree), the recursion stack has a depth of O(n), but for a balanced tree, the space complexity is O(h), where h is the height of the tree.

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: true
• Explanation: An empty tree is trivially symmetric.

1. Single Node Tree:

• Input: root = [1]
• Output: true
• Explanation: A tree with only one node is symmetric.

1. Symmetric Tree:

• Input: root = [1, 2, 2, 3, 4, 4, 3]
• Output: true
• Explanation: The tree is symmetric around its center.

1. Non-Symmetric Tree (Unequal Subtree Values):

• Input: root = [1, 2, 2, null, 3, null, 3]
• Output: false
• Explanation: The tree is asymmetric because the subtrees do not match in structure.

1. Non-Symmetric Tree (Different Structure):

• Input: root = [1, 2, 3]
• Output: false
• Explanation: The structure of the tree is not symmetric.

Conclusion

LeetCode 101: Symmetric Tree is a problem that tests your understanding of binary tree structures and recursion. The recursive approach provides an elegant solution for checking whether a tree is symmetric by comparing its subtrees in a mirror fashion. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the tree. This approach efficiently handles trees of various sizes and structures, making it a suitable solution for the problem.