MIRRORTREE - Editorial

editorial
1

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:

    1. 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.
    1. In the main function isMirrorTree(), call isMirror() with the root of the binary tree.
    1. 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.