Symmetric Tree | Interview Problem

Introduction:

In this tutorial we are going to solve a good question which will clear your doubts on how BFS or level order traversal is useful to solve binary tree problems. this is basically a question from Leetcode, and it is really very good problem to practice BFS.

Problem Statement:

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:

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

Link:Leetcode Link

please make binary tree on paper by the given array above. and you will get a clear picture of the problem.

what we are going to do in this problem.

Solution:

As we know we are going to apply BFS to solve this problem. actually you have to just get one thing to solve this problem. we will perform BFS, but with little change or modification.

So first we will store the root->val in a vector or array of the left subtree. and during this we will first insert left child and then right child in the queue(as we are applying BFS).now we are done with left subtree.

Now, we will do level order traversal on right subtree. and here is the main thing . we will insert right child first and then left child into the queue. and then put the value of each level in the vector. basically we are storing the value of nodes of right subtree in this vector.

Final step is now compare vector of left subtree and right subtree. if both are same return true, otherwise return false.

Full Code:

bool isSymmetric(TreeNode* root) {

        if(root==NULL)

            return true;

        if(root->left==NULL && root->right==NULL){

            return true;

        }

        if(root->left==NULL && root->right!=NULL)

            return false;

        if(root->right==NULL && root->left!=NULL)

            return false;

        vector<int>leftPart; // to store left subtree

        vector<int>rightPart; //to store right subtree

        queue<TreeNode*>leftq; // to perform BFS on left subtree

        leftq.push(root->left);

        queue<TreeNode*>rightq; //to perform BFS on right subtree

        rightq.push(root->right);

//left subtree

        while(!leftq.empty()){

            TreeNode* temp=leftq.front();

            leftq.pop();

            if(temp!=NULL){

                leftPart.push_back(temp->val);

                leftq.push(temp->left);

                leftq.push(temp->right);

            }

            else{

                leftPart.push_back(0);

            }

            

        }

//right subtree

        while(!rightq.empty()){

            TreeNode* temp=rightq.front();

            rightq.pop();

              if(temp!=NULL){

                rightq.push(temp->right);

                rightq.push(temp->left);

                  rightPart.push_back(temp->val);

              }

            else{

                rightPart.push_back(0);

            }

        }

        int flag=0;

        if(leftPart.size()==rightPart.size()){

            for(int i=0;i<leftPart.size();i++){

                if(leftPart[i]!=rightPart[i]){

                    flag=1;

                    break;

                }

            }

        }

        if(flag){

            return false;

        }

        else{

            if(leftPart.size()!=rightPart.size())

                return false;

            else

               return true;

        }

    }

Conclusion:

This is really a good problem to understand the application of BFS. we all know BFS but always have a question in mind where we will use , how we will use.

Note:

In case of Binary Tree problem, we have four kind of traversal preorder, inorder, postorder and level order. so whenever you get a question on tree and we have to traverse the whole tree, then always think a solution in which we can apply one of these traversal.