Leetcode: 101. Symmetric Tree

Symmetric Tree (Iterative Approach)

Problem Description

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

Solution

To solve this problem using an iterative approach, we can use a queue to perform a level-order traversal of the tree. We enqueue the root node twice to initiate the process.

In each iteration, we dequeue two nodes from the queue, which represent two nodes at the same level. We compare their values to check if they are symmetric.

If both nodes are null, we continue to the next iteration. If only one of them is null, we return false as they are not symmetric. If their values are different, we also return false.

If the values are equal, we enqueue the left child of the first node with the right child of the second node, and vice versa. This ensures that the children of the current nodes are mirrored for the next level.

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr)
            return true;
        
        queue q;
        q.push(root);
        q.push(root);
        
        while (!q.empty()) {
            TreeNode* t1 = q.front();
            q.pop();
            TreeNode* t2 = q.front();
            q.pop();
            
            if (t1 == nullptr && t2 == nullptr)
                continue;
            if (t1 == nullptr || t2 == nullptr)
                return false;
            if (t1->val != t2->val)
                return false;
            
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        
        return true;
    }
}
    

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. We need to visit each node once.

The space complexity is O(m), where m is the maximum number of nodes at any level in the binary tree. In the worst case, the queue will store all the nodes at the same level, which can be at most n/2 nodes in a complete binary tree.

Example

Consider the following binary tree:

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

We can use the provided code to check if the tree is symmetric:

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(4);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(3);

Solution solution;
bool isSymmetric = solution.isSymmetric(root);
    

After executing the code, the value of isSymmetric will be true since the tree is symmetric.

Conclusion

In this blog post, we explored an iterative approach to check if a binary tree is symmetric. We discussed the solution using a queue for level-order traversal, provided the corresponding C++ implementation, and analyzed the time and space complexities. Additionally, we demonstrated an example usage of the code.

Feel free to try out the code with different binary trees to check for symmetry!