Symmetric Tree
Problem Description
Question
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
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. -100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Solve it on LeetCode
Approaches
1. Recursive Approach
The symmetric tree problem can be solved by recursively checking if the left subtree is a mirror of the right subtree. More formally, two trees are a mirror of each other if:
- Their two roots have the same value.
- The right subtree of each tree is a mirror of the left subtree of the other tree.
Intuition:
- A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
- For each node, compare the left and right subtrees for mirror-like properties.
- This can be implemented using a recursive function that checks these properties at every node.
Steps:
- If both nodes are null, they are symmetric.
- If only one of the nodes is null, they are not symmetric.
- Check if the current nodes have the same value.
- Recursively check the left and right children.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
- Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.
2. Iterative Approach using Queue
Another way to solve the symmetric tree problem is by using an iterative approach with a queue. The idea is similar to the recursive approach, but we employ a queue to imitate the function call stack.
Intuition:
- Instead of recursion, maintain a queue to process nodes in layers.
- Enqueue pairs of nodes to be compared.
- If at any point, the nodes are not symmetric, return false.
Steps:
- Use a queue to store nodes for comparison.
- Initially, enqueue the left and right child of the root.
- While the queue is not empty, extract a pair of nodes.
- If both are null, continue the loop.
- If one is null, return false.
- If their values differ, return false.
- Enqueue the children of the nodes in the order to maintain the symmetry.
Code:
Complexity Analysis
- Time Complexity: O(n), as every node is processed once.
- Space Complexity: O(n), where n is the number of nodes in the queue at any level (widest point of the tree). For a perfectly balanced tree, this would be approximately h/2 nodes, or n/2/3 in the worst case.