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.

Lessons Learnt

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.

How useful was this post?

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...

Follow us on social media!

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

Let us improve this post!

Tell us how we can improve this post?

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments