Mirror Tree

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Check if binary tree is mirror of itself (symmetric). Recursive left-right comparison.

Algorithm

1isMirror(left, right): both null -> true. One null -> false. left.val==right.val and isMirror(left.left,right.right) and isMirror(left.right,right.left).

Common Pitfalls

•Same as LC 101. Recursive or iterative with queue checking pairs. O(n).

Mirror Tree.java

Java

// Approach: DFS. Recursively swap left and right children of every node.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
    // Function to convert a binary tree into its mirror tree.
    void mirror(Node node) {
        dfs(node);
    }

    void dfs(Node node) {
        if (node == null)
            return;

        dfs(node.left);
        dfs(node.right);

        Node temp = node.right;
        node.right = node.left;
        node.left = temp;
    }
}

Was this solution helpful?