Coding

# LeetCode Symmetric Tree Solution

0
(0)

Given the `root` of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

```Input: root = [1,2,2,3,4,4,3]
Output: true
```

Example 2:

```Input: root = [1,2,2,null,3,null,3]
Output: false
```

Constraints:

• The number of nodes in the tree is in the range `[1, 1000]`.
• `-100 <= Node.val <= 100`

Follow up: Could you solve it both recursively and iteratively?

Solution

Key thing to observe here (which I missed initially) is that we need to find out if this binary tree is cut into half at the center and if left half is shown in the mirror, the mirror image should be equivalent to right half. See the central line in example one and visualize that in your mind.

Once it got clear to me about the problem, I started thinking about the solution. For any binary tree problem, my first thought process is always Can I solve it through recursion? On first try I could not solve it. I saw a hint and then got one important thing here to keep in mind. That around the center left and right child should be equal. And then left’s right child should be equal to right’s left child. And left’s left child should equal to right’s right child. We can now implement this recursively.

Below is the Java code for the same.

``````/**
* Definition for a binary tree node.
* 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 Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || isSymmetricFun(root.left, root.right);

}

private boolean isSymmetricFun(TreeNode left, TreeNode right) {
if (left == null || right == null) return left == right;
else if (left.val != right.val) return false;
else return isSymmetricFun(left.left, right.right) && isSymmetricFun(left.right, right.left);
}
}``````

Once I checked on efficiency for the same on LeetCode I saw the following results.

For binary tree problems, recursion can be thought as one of viable and easy to understand solutions. If you are able to derive right recursion function with right input parameters you have almost solved the problem.

I have given a try for recursive solution. Why don’t you guys give it a try for iterative solution and see if that is more efficient in terms of time and space complexity.

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?