Symmetric Tree solution

This is a solution that aims to solve mostly the LeetCode problem number 101 Symmetric Tree.

Problem

Given a binary tree, check whether it is symmetric at its root. You can understand the symmetry of a binary tree as a condition when the left branch of the tree from the root node is the mirror reflection of the right branch of the root node.

For example, this tree is symmetric, left branch from root is mirror reflection of right branch.

       1
     /   \
    2     2
   / \   / \
  3   4 4   3

However, this example of the tree is not. This tree is not symmetric; the left branch from the root is not a mirror reflection of the right branch.

       1
     /   \
    2     2
     \     \
      3     3

Constrains

Definitions: A root is generally noting start of the tree. It can be interchangeably used as a start node for a branch of arbitrary length. A leaf is a node with no children. A branch is a node connecting one parent node and one or two child nodes.

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

When we look at problem constraints, we can see no condition we should be worried about. The number of nodes is relatively small, and the value of nodes is not essential. We care only about geometric symmetry. We will not really work with values (accept comparing value nodes on the tree levels).

Symmetric Tree problem solution in Java

For TreeNode we will use predefined class which is provided by LeetCode platform.

/**
 * 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;
 *     }
 * }
 */

The basic idea of our solution is to try to solve this problem in the simplest best-case scenario. We will take our simplest best case scenario from above, and we will bring its left and right node into the helping function isSymmetric(TreeNode left, TreeNode right). Here we will take all the possible scenarios of we will return the answer consequently.

class Solution {

    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return false;
        }
        return isSymmetric(root.left, root.right);
    }

    // Eliminate all the options
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if(left == null && right == null) {
            return true;
        }

        if((left == null && right != null) || (left != null && right == null)) {
            return false;
        }

        if(left.val != right.val) {
            return false;
        }

        if(!isSymmetric(left.left, right.right)) {
            return false;
        }

        if(!isSymmetric(left.right, right.left)) {
            return false;
        }

        return true;
    }
}

First we will ask if the nodes are null. If they are tree is symmetrical. For example, tree with one element is symmetrical for left and right node null.

Then we will take negative scenarios. What if left node has value and right is null? Or vice versa? The tree is not symmetrical.

Do children nodes values equal? If yes, the tree is symmetrical. If not, the tree is not symmetrical.

And here comes the last part. Now we will take children nodes of children nodes of the root, and we will compare them against each other. But we will do it to compare the right sides for children of mirrored reflection. We are doing recursion, and we need to return a certain value as default. As we have accounted for all other cases in previous lines, if all is symmetrical, the tree is symmetrical, and we can return the default value as true. Return value gives us a hint on how to handle the recursive call on unsymmetrical children of the children. If they are not symmetrical we need to return false. And since we put recursive call into if evaluation condition, negating the return value we can enter the if block and return false. This will secure us a recursive call on all conditions.

Note to remember: Try to solve this problem for the simplest best case scenario, when a tree has three symmetric levels. Solve all cases for the root node, continue recursively.

The recursive solution might be complex at first. But by slow approach debunking on smaller pieces, this recursion can be build up quickly.

Conclusion

This article showed you one recursive approach how to solve LeetCode problem number 101 regarding the symmetric tree. Start slowly with a simple best case scenario and figure out all the cases of symmetry of the tree on the way. A slow approach that considers all issues should help you to build an easily recursive solution.

Thanks for reading. Like us? Refer us to your friends and help us grow.

Have you found a similar question on other platforms? Let us know in the comment to adjust the description, and your contribution will help others be better at solving this problem.