Symmetric Tree

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Check if binary tree is a mirror of itself. Recursive pair comparison.

Algorithm

1isMirror(left, right): both null=true; one null=false; values differ=false; recurse: isMirror(left.left,right.right) && isMirror(left.right,right.left).

Common Pitfalls

•Same as LC 101. Compare outer pair and inner pair simultaneously.

Symmetric Tree.java

Java

// Approach: DFS. Tree is symmetric if left subtree mirrors right. Recursively compare left.left with right.right etc.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

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

class Solution {
    public boolean isSymmetric(Node root) {
        if (root == null)
            return true;

        return check(root.left, root.right);
    }

    public static boolean check(Node head1, Node head2) {
        if (head1 == null && head2 == null)
            return true;
        if (head1 == null || head2 == null || head1.data != head2.data)
            return false;

        boolean left = check(head1.left, head2.right);
        boolean right = check(head1.right, head2.left);
        return left && right;
    }
}

Was this solution helpful?