L18. Check it two trees are Identical or Not | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@mukeshprajapati7524]

nxksisd

[@AmitKumar-je9qo]

Dp plzee😑😑

[@vedantjain1280]

my approach: if(p == NULL && q== NULL) return true; if(p == NULL || q== NULL) return false; if(p->val != q->val) return false; return isSameTree(p->right, q->right) && isSameTree(p->left, q->left) ;

[@theexplorer9012]

same bro just wrote exactly same

[@whileforloops5671]

Man the simplicity of the code is crazy awesome work dude

[@rakshayadav1892]

Python code: class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True if not p: return False if not q: return False if p.val!=q.val: return False return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

[@coldcoke9254]

I don't know about others but I got confused here a little bit, and it took me quite a while to understand why we are returning like this: return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); So let me try my best to explain to my fellow leetcoders who are also new to Binary Trees: if it is false: we return false no need to traverse the tree further. But what if they are equal we can't just return true since we need to check the tree down further so we return true and we check the left subtree and then the right subtree. Hopefully you understand now. P.S. We first the check the root node then we check the left subtree and then the right subtree similarly and when we reach null on both sides we return to the calling function.

[@shivangisrivastava1158]

always blown by your short crisp code! 👏 amazing

[@the_humble_lazy]

honest review: the quality of striver's teaching is far far superior than gfg self paced course...........thanks a lot for what you have done for the community❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤

[@mukulupadhyay4656]

no I don't think so

[@adityasrivastava7563]

Gfg self placed course is not updated, otherwise it's not bad...

[@ayushuniyal2586]

agreed:)

[@itikalamba3629]

Right I had also enrolled the gfg course but still learning from strivers videos

[@aadeshsharma0001]

You r my bajrangbali to my fear of trees. Thanks for this amazing tree series

[@bharath890]

The way you explain step by step...!!!!

[@lifehustlers164]

Completed 19/54 (35% done) !!!

[@laxmipasi2059]

if we are using any traversal some cases are failing because for few case will get same traversal values. eg. p =[1,1] q = [1,null,1] so I don't think we can use traversal

[@Shubhodeep-xv8mh]

Push some arbitrary constant value(out of node->val constraints, for example INT_MIN or INT_MAX) in the vector whenever you encounter a null node while traversal.

[@laxmipasi2059]

@@Shubhodeep-xv8mh didn't get can you provide psuedo code

[@Shubhodeep-xv8mh]

@@laxmipasi2059 In the preorder traversal function, for condition of null nodes, add - if (node == NULL) { pre.push_back(INT_MIN); // arbitrary value lesser than min possible node->val return; } In your example in the above comment, whenever we encounter a null left node as in q, we push this constant INT_MIN in the vector which helps us differentiate it from p where the right node is null.

[@Aryan-rh4ek]

@@Shubhodeep-xv8mh Thanks bro. it worked out for me

[@mriduljain1981]

completed lecture 18 of Tree playlist.

[@your_name96]

my code: if(!p and !q)return true; // both null if(!(p and q))return false; // if one null and other not null return sol(p->left,q->left) and sol(p->right,q->right) and p->val == q->val;

[@vikasgowdalv770]

Hey! You did almost all problems using recursion. But interviewers expect us to do in iterative manner

[@sravan8643]

??

[@aditya14-02]

Bhai dekh wo iterative bhi kara rha hai aur

[@gautamjh]

Iterative Solution using queue : bool isSameTree(TreeNode* p, TreeNode* q) { queue Q; if(!p or !q) return p==q; //If both roots are null Q.push(p); Q.push(q); //Push both the roots in the queue while(!Q.empty()) { TreeNode* left = Q.front(); Q.pop(); //Store one node in left and pop TreeNode *right = Q.front(); Q.pop(); //Store other in right and pop if(!left and !right) continue; //If both nodes are null -> continue if(!left or !right) return false; //If one of them is null, simply return false if(left->val != right->val) return false; //If they are not equal, return false //Push left childs of both nodes Q.push(left->left); Q.push(right->left); //Push right child of both nodes Q.push(left->right); Q.push(right->right); } return true; }

[@amanbhadani8840]

@@gautamjh Why dont You check the node while pushing in queue,whether its null or not,it may reduce your few lines of code.

[@utkarshsharma6650]

what's the difference? logic is similar, it's just that the iteration is done using a queue. rest, the conditions, the logic remains the same, buddy :)

[@prabhakaran5542]

Understood ❤

[@gangsta_coder_12]

Loving your tree series very much 👌👌👌

[@bhavkushwaha]

Thankyou Striver, Understood!

[@stith_pragya]

Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻

[@y-be2gf]

You are explanation are very good keep making videos❤

[@per.seus._]

UNDERSTOOD

[@cinime]

Understood! So smart explanation as always, thank you very much!!

[@BharathS-qw9cl]

Bhaiyya, as u said that recursion could be optimised by stopping any further calls when any one the calls return true, I tried out this one here class Solution { public: bool checkusingpreorder(TreeNode* p, TreeNode* q){ if(p == NULL && q == NULL) return true; if(p == NULL || q == NULL || p -> val != q -> val) return false; if(checkusingpreorder(p->left,q->left) == false) return false; if(checkusingpreorder(p->right,q->right) == false) return false; return true; } bool isSameTree(TreeNode* p, TreeNode* q) { return checkusingpreorder(p,q); } };

[@DhananjayKumar-vn5tc]

waiting for dp series and this playlist is very good.

[@y-be2gf]

Bro you are just wow ♥️ love u brother

[@surajJoshiFilms]

Space Complexity will be O(Height of Tree)?

[@karthikvaradharajan6094]

Can we try a new approach of override equals method in Tree Node class checking data, left node and right node?

[@sarthaksharma9677]

Hey Striver, had a quick query What if I have a vector and push_back some grabage value like 0.001 into it when nullptr is encountered and then compare thiese vectors for both, MY DOUBT IS this approach works for pre order but not for inorder, I am not able to think of a case in which pre order would fail but logically I feel there could exist a case where this fails like inorder traversal and am not able to justify that preorder would be correct conceptually.

[@apmotivationakashparmar722]

Thank you so much

[@PrakharKulshrestha-q6e]

Understood

[@divyareddy7622]

thank you god for giving us striver

[@chetanraghavv]

But how can we tell based on only preorder, I think different trees can have same preorder!

[@Ritik-ww7ro]

same doubt, I think we also need inorder traversal.

[@solarchat9413]

We can't

[@harshitsaxena7205]

@@Ritik-ww7ro have you get to know the answer then please explain

[@Shivi32590]

thank you

[@akshatchaube1213]

L 18 done

[@DSAMADESIMPLE]

Amazing Striver Bhaiya

[@abhinanda7049]

understood

[@harshitjaiswal9439]

understood.

[@parthsalat]

Understood kaka

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@UECAshutoshKumar]

Thank you sir

[@androiddev884]

how is space complexity O(n)

[@kireetipudi8106]

p = [1,1] q = [1,null,1] inorder is not working for this case

[@harshitshukla1974]

at 3:38 you said that we can do it with level order traversal. how cane we do this with level order traversal. -> suppose we have two trees (both of 2 nodes only) where root of both trees is 1 and in the first tree we have left child as 2 and in the second tree we have right child as 2. In this case the level order traversal will result in saying that they are same but actually they are not. Please anyone tell me am I missing something in the level order traversal?

[@manchestercity-levi]

we'll have to push the nullptr as well in the queue for proper comparison .

[@adarshkumarrao3478]

UNDERSTOOD❤

[@jiotv7923]

how the space complexity is O(N)? can someone explain?

[@artofwrick]

Recursion stack

[@krishnavamsichinnapareddy]

Understood 👍

[@vishalsrivastava3137]

Your videos are always great 👍

[@PalakMittal]

Why preorder, inorder and postorder are giving error if there is a null node in between, and level order traversal or bfs is working fine?

[@codingwithanonymous890]

mine is working

[@yadneshkhode3091]

aapne kidhar toh code me hagg diya hai

[@Sumit-lr1qj]

@@codingwithanonymous890 code bhej bhai

[@enigmanarratives1]

class Solution { public: bool help(TreeNode* p,TreeNode* q){ if(p==NULL && q==NULL) return true; if(p==NULL || q==NULL) return false; if(p->val!=q->val){ return false; } return help(p->left,q->left)&&help(p->right,q->right); } bool isSameTree(TreeNode* p, TreeNode* q) { return help(p,q); } }; its working

[@suvanshmahajan5902]

"us"

[@ayah717]

thank you bhaiya

[@NishilPatel-d2m]

if(p->val == q->val) { return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); }else return false;

[@aravindmiras3708]

bro you drop this

[@rishabhteli2339]

Short videos are OP :)

[@huungryyyy]

😊😊😊😊😍😍😍😍

[@nishant3904]

Thank You !

[@rushyya]

UNDERSTOOD! THANK YOU🙌

[@Code_Solver]

Understood bayya

[@gautamjh]

Iterative Solution using queue : bool isSameTree(TreeNode* p, TreeNode* q) { queue Q; if(!p or !q) return p==q; //If both roots are null Q.push(p); Q.push(q); //Push both the roots in the queue while(!Q.empty()) { TreeNode* left = Q.front(); Q.pop(); //Store one node in left and pop TreeNode *right = Q.front(); Q.pop(); //Store other in right and pop if(!left and !right) continue; //If both nodes are null -> continue if(!left or !right) return false; //If one of them is null, simply return false if(left->val != right->val) return false; //If they are not equal, return false //Push left childs of both nodes Q.push(left->left); Q.push(right->left); //Push right child of both nodes Q.push(left->right); Q.push(right->right); } return true; }

[@dipanshusingh]

Loved the video. Thanks for it.❤

[@engineer8340]

thankyou bhaiya

[@_hulk748]

Understood sir🙇‍♂❤🙏

[@lavanyaprakashjampana933]

we love your content and we love you..🖤

[@rupampakhira8132]

Understood

[@snehagoyal4978]

bool isSameTree(TreeNode* p, TreeNode* q) { if(p==NULL && q==NULL)return true; if(!p || !q || p->val != q->val)return false; return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); }

[@AbhishekKumar-td5zu]

understood❤❤

[@savalalingeshreddy6750]

understood

[@poojaroy7211]

completed

[@poetrystation3178]

why everyone is appreciating even though his code is passing on 2 test case in gfg ?? honestly i have been following his video but koi bhi code run nhi hota hai chatgpt se 10 baar correct krva kr run hota hai in sir ki itni hype q hai market mei ??

[@monismomin6759]

US!!

[@nagavedareddy5891]

Huge respect...❤👏

[@pritishpattnaik4674]

So easy man

[@deepakgurjar3746]

How can we directly compare p==q isn't there refrences are different in memory, for that we have to compare there value/data at each node????? bcz this same concept of refrences earlier used in video of problem: Intersection Point in Y shaped linked list I done according to that and my soln is accepted but i also want to clear my concept,bhaiya plz replyyyy??????

[@deepakgurjar3746]

MY CODE:- class Solution { public: int solve(TreeNode* p,TreeNode* q){ if(p==NULL&& q==NULL) return 0; if(p==NULL && q!=NULL|| p!=NULL && q==NULL) return -1; if(p->val != q->val) return -1; int left= solve(p->left,q->left); if(left==-1) return -1; int right= solve(p->right,q->right); if(right==-1) return -1; return 0; } bool isSameTree(TreeNode* p, TreeNode* q) { return (solve(p,q)==0)?true:false; } };

[@deepakgurjar3746]

i get a little clarity that we are comparinthem only when one of them is null and in this case one is null and other is not null then we get our ans....also if both are null then they have same refrences i guess that why our solution is working perfectly fine for all cases?

[@ishwaripednekar5164]

Amazing

[@enigma2777]

Understood 🖤

[@ronakslibrary8635]

US

[@Cool96267]

Good code

[@gouravkumarshaw5467]

hello

[@momilijaz271]

life saver code!!!

[@sahilkumarsingh8517]

Understood😁

[@shubham6215]

Thanks 👍👍

[@swapnilsrivastava9407]

best one

[@UECSoumyaRay]

Keep it up

[@gauravbisht8487]

🌲

[@utkarshsharma6650]

understooood. thanks :)

[@satyamroy3783]

striver u rock💥

[@ajayypalsingh]

💚

[@venkatvenkat-hj2gq]

i am loving this

[@blakestudy1870]

nice video

[@vinaygupta2369]

❤️❤️❤️

[@ishaankaustav727]

💚💚

[@vani.sharmaa]

us

[@cenacr007]

us

[@vibhu613]

💖💖

[@aviralsharma9260]

class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p == NULL && q == NULL) return true; else if (p == NULL || q == NULL) return false; return ((p -> val == q -> val) && isSameTree(p -> left, q -> left) && isSameTree(p-> right, q -> right)); } };

[@shubamgoswami]

done \

[@Ritik-ww7ro]

how can we tell based on only preorder, as 2 trees can have same preorder . I think we also need to check inorder traversal. If anyone can clear ?

[@abhishekpilla8857]

Even I have the same doubt 2 Trees can have pre orders traversal same...either we have to to 2 traversals and one should be inorder

[@sahilverma3976]

The code still works because we're checking the traversals of both the trees simultaneously. Take two different binary trees with the same preorder traversal, dry run the code and you'll get the idea about what I'm saying.

[@somyapratapsingh9849]

1000th like :)

[@NishilPatel-d2m]

class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p == NULL && q == NULL)return true; // base cases if(p == NULL || q == NULL)return false; if(p->val == q->val) { return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); }else return false; } };

[@KaushikSharma-c3q]

.

[@himanshidafouty347]

Understood

[@sarankumaar6009]

"us"

[@jordanpaul8697]

Understood