Prerequisites: Binary tree, BT traversal.
Problem: Given a binary tree, check whether it is a structural mirror of itself (i.e., structurally symmetric around its center).
Solution Approach: Similar to Identical trees problem, this one can also be solved using a recursive approach to check if a binary tree is a structural mirror of itself. Two nodes are considered symmetric if their subtrees are symmetric. The algorithm recursively compares corresponding nodes in the left and right subtrees.
Algorithm:
-
- Implement a recursive function isMirror() that checks if two nodes are symmetric.
- If both nodes are NULL, they are symmetric (base case).
- If only one of the nodes is NULL, they are not symmetric.
- If both nodes are non-NULL, check if their left and right subtrees are symmetric recursively.
- If the values are equal and both subtrees are symmetric, return true; otherwise, return false.
- Implement a recursive function isMirror() that checks if two nodes are symmetric.
-
- In the main function isMirrorTree(), call isMirror() with the root of the binary tree.
-
- Print “YES” if the tree is a structural mirror and “NO” otherwise.
Time Complexity: O(N), as we need to traverse each node at least once.
Space Complexity: O(1), as we don’t need any extra space.