Mirror Tree

JavaView on GFG

Time: O(n)

Space: O(h)

Problem Overview

Check if binary tree is mirror of itself (symmetric).

See our study guide for structured GFG and LeetCode practice.

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?