Symmetric Tree

Companies:

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);
}
}
```
Scroll to Top

Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.