Symmetric Tree

Symmetric Tree Link

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1

   / \

  2   2

 / \ / \

3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

   1

  / \

 2   2

  \   \

   3    3

Follow up: Solve it both recursively and iteratively.

Explanation

For a tree to be symmetric, it’s left subtree should be a reflection of it’s right subtree.

That means, the left subtree should be equal to the right subtree and vice-versa.

This is done by implementing a tree based on the given inputs and checking for it’s symmentry either using recursive algorithm or using iterative appraoch.

Complexity Anaysis:

• Time complexity: O(n).
• Space Complexity: O(n).

Implementation

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
  }
class Solution1 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null || right == null) {
            return left == right;
        }
        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
    }