Test If A Binary Tree Is Symmetric ("Symmetric Tree" on Leetcode)
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- Code - backtobackswe....
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program to check if a binary tree is symmetric in structure as well as value.
A binary tree is symmetric if we can draw a vertical line down from the root and the left and right subtrees are mirrors of each other in structure and value.
The least this could be is O(n) time because we have to inspect all n nodes values to ensure that they conform to the tree being symmetric.
All we need to do is traverse the tree correctly with our recursion checking pairs for conformity.
The Conditions
If the root is null, the tree is symmetric.
Our checking function will take 2 nodes in to compare for symmetry.
Our Base Cases
If both nodes passed in are null, by default we have a symmetric tree.
If one node is null and the other is not, then we have incongruence, the tree is not symmetric since a pair failed.
If both nodes are null, then compare values. If values are equal, then good. Go left and go right.
How do we come up with this on the spot?
First recognize the base cases.
Then recognize we will need some way to compare pairs of nodes since that's what matters when checking for symmetry.
Even if this were an array that is how we would do it, pairs of indices.
Then recognize the way the recursive case must continue the work on the way down and your solution would look like this at the end.
Complexities
Time: O(n)
Space: O(h) (as we discussed, it can't really be O(n) worst case since
the first check would fail if the tree is skewed. The worst case IS O(h))
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++++++
This problem is problem 10.2 in the book Elements of Programming Interviews by Adnan Aziz
![[[OFFICIAL MV]] เอิ้นขวัญให้อ้าย- อ๊ะอาย สกุณาพร | ค่ายเพลงเป็นหนึ่ง](http://i.ytimg.com/vi/83x6L3X3qh0/mqdefault.jpg)
Table of Contents:
Video Setup 0:00 - 0:18
Problem Introduction 0:18 - 2:45
Find The Pattern With An Array 2:45 - 4:20
Find The Pattern With A Binary Tree 4:20 - 6:48
The Code. 6:48 - 9:17
Time & Space Complexity 9:17 - 10:58
Apply This To Other Recursive Problems 10:58 - 12:05
As with every video, I'm not perfect, I hope I didn't make any gross mistakes in the video. If all is well, great, this is the explanation for how to test if a binary tree is symmetric.
Please don't feel sorry for being loud,that's your speciality when you talk ;
it feels like a professional teacher is teaching and he wants all his students to pass in any cost.
lol ok, old videos had bad gear and no mic, and yeah I gave my life for 1.5 years to make these videos I want everyone to pass at any cost lol
The energy in your explanation is just awesome,it makes everyone to listen your words with great concern,it is really true that positive person give off positive energy
yes and thanks
Awesome video! I think you decouple this problem quite elegantly. Trying to solve a problem in a recursive way is not easy. You did a great job!
thanks
Damn, if my interviewer had your energy in this video, i'd be half pumped / half having an anxiety attack. But anyways, I'm on a binge on your videos, thanks for the help!
yeah, old video, sorry.
I love this energy! Keeps me interested, stay pumped up
@@parthpawar7837 ye
The best explanation. Even the bubbling up guys 😆 like nick white and kevin fades in front of you! Increased my confidence dude. Who the hack disliked!! Complete disguise!
And l Liked my own comment ✌️
duddeeeeeee! thankssssss!!!! I needed you in my life and I didn't even know until now
haha
lmao, "sustain our lives" i felt that
That was a fantastic explanation!!...It very well shows how passionate you are about your work...and believe me you can make people love data-stuctures..
thx
Thankss Dudeee!!! finally, after this video i solved this problem successfully.
great
Your editing has improved a ton! Keep up the good work.
I know haha
Watching on X-mas day after 2 years :)
Your video is so good. The explanation is super clear.
Woah your energy boosted me as well. Thanks!
sure
U deserve more likes and subscribers.
I know, eventually
@@BackToBackSWE I guess after watching your video, every one rushes to leetcode to solve that instead of a like😂😂
very nice, you are the best youtuber who can explain leetcode problems clearly and make them easy to understand.
thanks
4 years later, still great
You are so brilliant !! Thanks for making these videos.
sure
thanks sir for the simplest explanation i have came across so far
Salute you dude, hands down please make more problems about the graph theory, you are mindblowing
ok
I studied at UMD. I am proud of you man!
Let's put turtles on the map 🐢🐢
Thanks for the explanation boss. The space complexity part was great as well Call stack etc. Can you make a quick video on Min depth of binary tree. Algthough I understand it. But its a bit tricky!
yeah
like your passion dude
yeah
I think the space complexity is also O(n). The worst case is basically a symmetric list with the middle as the tree root. O(n/2) ≈ O(n), in terms of space for the stack frames
Awesome !!!! You have really good teaching skills.
Thanks
Thanks for this video I really like the way you explain this problem
Could I use an in order traversal to push all the values into a vector, then do a palindrome test in the vector?
how so?
Yes you can do that way, but before applying Inorder traversal convert the tree into complete binary tree.
@@prabhjyotsingh139 oh yeah I get it now, yeah you can do it like that as long as you make the provision for null nodes
Yes you can, the problem is that the time complexity will be O(n) in every case. The recursive solution is O(n) in worst case.
Thank you! I've been watching MIT lectures on data structures and algorithms and when I don't understand something, I always get a super clear explanation here! You're terrific at explaining things
Thank You!!
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
Super thanks!
sure
Best explanation, hands down 👌
thx
You’re just a legend!
Nice explanation! Thanks for the video!
sure
The energy is infectious 🚀
good as always :)
thanks!
thx
I have an interview in 2 days. If only I had seen your videos earlier :'(
haha yeah
Loved it
thanks
you are great man !!! thanks
thx.
7:47 nice rhyming symmetry
Fantastic videos, man! Thank you so much for your work! P.S.: It's very sad that you don't have many comments/views, but most importantly you're delivering the quality, so all these things will come soon! Awesome!
You have no idea how much that means to me! :)
Every day I wonder if it is worth it to continue doing this. I have like 300 questions I want to cover (that I did while learning) and I realize that is a HUGE year-long project at the best if I keep it up.
Normally videos have this breakdown:
1 hr notes
1 hr shooting
2-6 hours editing
30 minutes to publish
Not sure how I can keep it up during school but we will see (it starts Jan. 28th)
So yeah I think they are ok but holy crap they take a long time. I have a long story behind why I do these videos, but I have like an internal thing keeping me going despite knowing that literally no one watches right now.
Thank you so much, I really appreciate this.
@@BackToBackSWE Keep doing them. These vids are the best. Listen if I get a the job I want from these vids I'm donating you 500 bucks!
@@qaipak1 haha ok
@@BackToBackSWE please continue if you can and have the desire! You are amazing!
@@LilyEvans1996 workin' on it
This is great, except you missed 5:13 in the table of contents! :)
hahahahaha
Hey man you are so great ! haha
thanks
Brilliant
thanks
Please make more videos. why have you stopped making videos? Your channel is great bro.
I'm working at Twitter and don't make public videos since we run backtobackswe.com
Bro please upload more video on trees. I am waiting for that.
ok
Love it mannn !!
just one comment, try to decrease the energy just a little/
Thank you so much !!
ye
Thank you!
sure
You are just amazing !!!!!!
thx
pause at 6:43 and you can see the solution. Otherwise you're standing in front of it the whole time dude.
sorry, this is an old video
@@BackToBackSWE still dope for an old vid
Thank you, I did inorder traversal of the tree and then did palindrone . It passed 187 cases but failed 188 th case.
nice!
Same here.
@@Kev1nTheCoder can you tell at which test case is it failing ???
@@neeravganate9562 Sorry I don't remember. I checked the Leetcode but it turns out they changed their test cases.
@@Kev1nTheCoder np got it now
Thank you, Sir, this helped
This was really helpful. Thanks a lot.
Can you please make a video on Diameter of Binary Tree? It's really confusing and I am stuck on it. It would be really helpful if you could do that. Thanks
yeah
@@BackToBackSWE thanks
@@shashwatagrawal8412 sure
Thanksssss!!!
funny and great explanation ) thanks a Lot ))
sure
so good!
thanks!
But how to do it iteratively?
uh, I'd need to refresh myself on this problem
LOL, your endings. You can just say "thanks and see you next time" but I guess if you did that your endings wouldn't be special.
yeah haha, gotta be cool
One day you will know how to end your videos. We have faith in you.
wut
@@BackToBackSWE 11:52
Lovely video bruh. May the $$$ be with you.
idc about $$$ only ok, ik that it may seem that way but I just need to fulfill my vision. And thx
You're the one
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
awesome :)
At first i thought he was Lewis Hamilton :D
You were really yelling in the early videos 😆
Yeah I was, things improve over time if you just stay with them. A life lesson. We get better everyday.
Oh lord I might as well have a heart attack right now : D
what
@@BackToBackSWE Still teaching in the same library room now?
Also, do you have any tips on how to remember the code for problems you've done, thanks!
RIP to the people who disliked this
the video is ok
Why are you standing in front of the code 99% of the time?
You're moving way too much and it's a bit distracting otherwise you're a wonderful instructor.
Very nice!!
thanks