5. Mirror Tree

The problem can be found at the following link: Question Link

Problem Description

Given a binary tree, convert it into its Mirror Tree by swapping the left and right children of all non-leaf nodes.

Example 1:

Input:

        1
       / \
      2   3
         /
        4

Output:

        1
       / \
      3   2
       \
        4

Explanation:

Every non-leaf node has its left and right children interchanged.

Example 2:

Input:

        1
       / \
      2   3
     / \
    4   5

Output:

        1
       / \
      3   2
         / \
        5   4

Explanation:

Every non-leaf node has its left and right children interchanged.

Constraints:

• 1 ≤ number of nodes ≤ $10^5$

• 1 ≤ node->data ≤ $10^5$

My Approach

Recursive DFS (Top-Down)

1. Base Case: If the node is NULL, return.

2. Recursively traverse the left and right subtrees.

3. Swap the left and right children of the current node.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N), since every node is visited once.

• Expected Auxiliary Space Complexity: O(1) OR O(H) for recursive DFS (H = height of the tree).

Code (C)

void mirror(Node *n) {
    if (!n) return;
    mirror(n->left);
    mirror(n->right);
    Node* t = n->left;
    n->left = n->right;
    n->right = t;
}

Note: The C code may show an error when compiled and run, but if you proceed with submission, it still passes all test cases.

For example, consider the input:

1 2 3 N N 4

The output after compilation and running:

1 3 2

Expected output:

1 3 2 N 4

Although there is a difference in output format during execution, submitting the code results in a successful pass for all test cases.

Code (C++)

class Solution {
public:
    void mirror(Node* node) {
        if (!node) return;
        mirror(node->left);
        mirror(node->right);
        swap(node->left, node->right);
    }
};

🌲 Alternative Approaches

2️⃣ Iterative BFS (Level Order)

class Solution {
public:
    void mirror(Node* root) {
        if (!root) return;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            Node* cur = q.front(); q.pop();
            swap(cur->left, cur->right);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
};

3️⃣ Iterative DFS (Using Stack)

class Solution {
public:
    void mirror(Node* root) {
        if (!root) return;
        stack<Node*> s;
        s.push(root);
        while (!s.empty()) {
            Node* cur = s.top(); s.pop();
            swap(cur->left, cur->right);
            if (cur->left) s.push(cur->left);
            if (cur->right) s.push(cur->right);
        }
    }
};

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Method	Pros	Cons
Recursive DFS (Top-Down)	🟢 O(N)	🟡 O(H)	Recursion	Simple and concise	May cause stack overflow for deep trees
Iterative BFS (Level Order)	🟢 O(N)	🔴 O(W)	Queue-based	Avoids recursion depth issues	Uses more memory for wide trees
Iterative DFS (Stack)	🟢 O(N)	🟡 O(H)	Stack-based	Explicit control over traversal order	Still uses extra space for the stack

Best Choice?

• For balanced trees, the Recursive DFS approach is fine.

• For deep trees, the Iterative BFS approach is preferable to avoid recursion depth issues.

• For explicit control and iterative processing, the Iterative DFS (Stack) approach is a solid option.

Code (Java)

class Solution {
    void mirror(Node node) {
        if (node == null) return;
        mirror(node.left);
        mirror(node.right);
        Node temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

Code (Python)

class Solution:
    def mirror(self, root):
        if not root:
            return
        self.mirror(root.left)
        self.mirror(root.right)
        root.left, root.right = root.right, root.left

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count