Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Disjiont Set Union-Find Data Structure | Code In C++

 Introduction:  In this tutorial we are going to write full program of disjoint set union find advance data structure in c++.  Problem Description: Disjoint Set Union (DSU) is an advance data structure, which basically uses in graph algorithms to find cycles. Codes:  Method1: Brute Force #include<bits/stdc++.h> using namespace std; int find(int f,vector<int>&dsuf){     if(dsuf[f]==-1)         return f;     return find(dsuf[f],dsuf); } void union_op(int from, int to, vector<int>& dsuf){     dsuf[from]=to; } bool isCycle(vector<pair<int,int> >&edge_list, vector<int>&dsuf){     for(int i=0;i<edge_list.size();i++){         int parent1=find(edge_list[i].first,dsuf);         int parent2=find(edge_list[i].second,dsuf);         if(parent1==pare...
Post a Comment
Read more

Target Sum | Backtracking Problem

Introduction: In this tutorial we are going to solve a problem "Target Sum" which is from leetcode. and believe me it's really a good problem to understand Backtracking(Recursion). and if you try to understand the problem as well as code you will get a clear picture of Backtracking. Problem Statement: Link To Problem You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and - . For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Solution: As given in question, we have two operation + and -. so we will make recursive call for + and - . and if we have sum as target and we have reached upto the last ind...
Post a Comment
Read more

Group Anagrams solution with explanation:Leetcode solution

what is Anagrams? suppose we have two strings and the characters present in both of the strings are same. then both will be called anagram of each other. eg:" rat" and "art" both are anagram of each other. the characters present in both string are same. eg: "raat" and "art" these are not anagrams of each other. and the reason is that the frequency of "a" in "raat" is 2. while the frequency of "a" in "art" is 1. so these are not anagrams of each other. in short two strings will be anagram of each other if they have same characters and the count(frequency) of each and every character must be same in both strings. Solution: There are different ways to solve this question, so here we are going to use Hashmap to solve this question. cause whenever there is need to search we should go with the data structure which use balanced binary tress or hashing. and we know that Hashmap  uses balanced binary trees. so using...
Post a Comment
Read more