@@buttofthejoke You have a point. Another approach I would have thought (more intuitively) was to keep two pointers left and right. And at each level move left pointer towards right and right pointer towards left. Check the elements which are encountered(like you’d do for checking palindrome.)
do a DFS on the right side favoring the right first. Do a DFS check on the left side favoring the left first, if any don’t match return false. Also works with BFS. O(n), half is traversed and other half is checked so between 1/2 to 1 of the n
Doesn't quite work. In your example [2,3,1,3,2], the tree isn't symmetrical, because after the root, a symmetric tree will always have an even number of items on each level- so your reverse check will pass even though the tree isn't symmetrical. Also, if say at level 2 (where root is level 0), you have no children on the right, and two children on the left- but both children are 3. Then you would have [3,3], which passes the reversal test even though the tree isn't symmetrical. There are ways to handle all these cases, but it will get messy fast.
Are you doing the full comparison two times? That is, when root1==root2==root, you execute sym(root1.left, root2.right) that verify all the tree but, you are also doing sym(root1.right, root2.left) that repeats all the comparison a second time. I think you should include before the las line of the function: if root1==root2: return sym(root1.left, root2.right) isn´t it?
@@zaringers to be clear I mean for this one specific question, sorry. As in, if an interviewer asked you this question then it would nearly be moot because you could have memorised an explanation. But like you say this could still be applied to a more challenging or unique problem
Understanding data structures and algorithms conceptually can be straightforward, yet unfamiliar syntax may lead to overly complex implementations. I think this is the reason why people find some “easy” problems complicated and difficult, at least that’s the case for me.
for some reason i just dont get recursion... i mean i get the general concept, but it feels like there's a mental block for me that stops me from actually creating any recursive solutions... if someone else ever got over that do lemme know how, it'd help a lot... i think its a pretty cool thing and i hate not being able to do it
I generally only use recursive if there are multiple paths, you can use looping but it can be annoying. Imo recursive is easier to read at the cost of performance however the impact varies. My advice write the code as a loop, if it works, improve it (if possible), then look to recursion. Look for tree and graph questions to look into recursion as they often have branching paths, not all solutions require recursion. Don't worry about not being able to do it, you'll often find recursive questions like Fibonacci or factorial are meant as introduction but are just significantly simpler and easier as a loop. You might actually already be doing it in the most efficient way.
thanks for sharing your insights. i'm not a newbie btw, i have a job n everything... and i never needed a recursive solution... ever.. so that makes it even more weird ...@@Bargi3
While this recursive looks smoother to eyes. It might be difficult to come up with the approach if not solved before. Also, it’s slow and consumes a lot of extra space that’s not needed. How about this? var isSymmetric = function(root) { var q = [root]; while(q.length){ var l=0, r=q.length-1; while(l
that was the first solution that came up to my mind. How can you solve this differently? It's a natural comparing process from the real life, is it not?
people saying this is unintuitive really need to study more or just see recursion more often. this is the most basic solution logically and can probably be reduced to like 5 lines (depending on your language perhaps). this probably isn't even the best solution. my expectation was that this would be the obvious solution that the interviewer is expecting but probably wouldn't get many points for. i feel like there is probably a more efficient algorithm that is iterative rather than recursive
My bad I was using too small of a number to see the limit for this... it's O(4(n + c)) | | - | || - || XX XX - XX XX List of steps we check "if not root1 and not roo2" 1 root, root 2 root.left, root.right 3 root.left.left, root.right.right 4 root.left.left.left, root.right.right.right 5 root.left.left.right, root.right.right.left 6 root.left.right, root.right.left 7 root.left.right.left, root.right.left.right 8 root.left.right.right, root.right.left.left 9 root.right, root.left 10 root.right.left, root.left.right 11 root.right.left.left, root.left.right.right 12 root.right.left.right, root.left.right.left 13 root.right.right, root.left.left 14 root.right.right.left, root.left.left.right 15 root.right.right.right, root.left.left.left 16 root.right, root.left 17 root.right.left, root.left.right 18 root.right.left.left, root.left.right.right 19 root.right.left.right, root.left.right.left 20 root.right.right, root.left.left 21 root.right.right.left, root.left.left.right 22 root.right.right.right, root.left.left.left 23 root.left, root.right 24 root.left.left, root.right.right 25 root.left.left.left, root.right.right.right 26 root.left.left.right, root.right.right.left 27 root.left.right, root.right.left 28 root.left.right.left, root.right.left.right 29 root.left.right.right, root.right.left.left Let's improve it just a little by changing 1 line. `return sym(root, root)` to `return sym(root.left, root.right)` if we need to add a check for if root exists, run that check before defining the internal sym method to meet the edge cases. 29 steps is still a bit extreme for only 7 nodes (1 of which we don't ever need to check as if it does or doesn't exist, has no impact on if it's square
@@ink2467 Considering your immature reply to a joke if anyone's the child it is you, putting that aside. Recursions can make sense but often times programmers jump to the recursive solution despite there being an iterative one which is basically always more efficient due to the underlying mechanics of recursions unless the compiler fixes it for you. So if this question isn't followed up with a more abstract one regarding the issues that often plague recursion it's a bad question.
@@ink2467 Besides depending on the tree structure used getting an in order list is going to be trivial, then cut it in half flip one (or just count from the back, whatever is supported in the language you use) and you've got the iterative solution not really difficult just takes ever so slightly more thinking.
@@ink2467If the tree is big, recursion can cause stack overflow. A loop would work with trees tens of thousands time bigger (until you runs out of memory).
no, it's a binary recursion. Inside of the sym function you only call sym twice. The fact that each call has two parameters is meaningless in terms of quantifying the degree of recursion. Also, you only visit each node once. This should run in O(n) time where n is the number of nodes in the tree, and O(logn) space. The space complexity is due to the fact that it's depth-first, so you'll only ever have a function call tower of at most the height of the tree.
You were probably breaking it down to make it more clear, but you could probably shorten that to a one liner. I'm not sure about python, but here's my Java implementation: private static boolean isSymetric(Node l, Node r) { return l == null && r == null || l.v == r.v && isSymetric(l.l, r.r) && isSymetric(l.r, r.l); }
@@tkorful However in this case I'd argue it is faster because his version has a bunch of if statements and that can cause branch predictions by the processor. If those predictions are wrong, you lose efficiency and processing cycles. I'm not sure about Python, but some compilers are smart enough to notice things like that and automatically optimize out those if statements, but if you do it yourself, it's even more assured.
a face for radio, and a voice for print. my condolences. this guy is a tool and he often doesn't know what he's talking about. guys/gals, if you're grinding leetcode, you're going to be disappointed in the long run. real long term success in software engineering is dependent upon your ability to be a clear communicator and an analytical thinker, not memorize solutions.
If you're being asked an algorithmic question during a job interview, you know you're one of the lower plebs. I have not been asked a single programming question for any job or project in the last 15 years, and I make 300k a year.
That's not true, at least in the US. FAANG will ask LeetCode style question to people with 20+ YOE for roles that pay 700k+. Of course they also have behavioral and system design questions, but LeetCode does not go away.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Easy but not ‘very easy’ for sure. It’s not totally intuitive to come up with sym(root, root)
but how else would you compare the two? if you've to compare two numbers, you've to pass those two numbers to a comparator function right?
@@buttofthejoke You have a point. Another approach I would have thought (more intuitively) was to keep two pointers left and right. And at each level move left pointer towards right and right pointer towards left. Check the elements which are encountered(like you’d do for checking palindrome.)
Think of doing a bfs traversal.
@@buttofthejoke something like this:
var isSymmetric = function(root) {
var q = [root];
while(q.length){
var l=0, r=q.length-1;
while(l
to be fair bsts arent exactly intuitive either in the sense that if you've never heard of it, you'd have to be a genius to come up with it on your own
do a DFS on the right side favoring the right first. Do a DFS check on the left side favoring the left first, if any don’t match return false. Also works with BFS. O(n), half is traversed and other half is checked so between 1/2 to 1 of the n
easier to make an inorder traversal of the tree (2, 3, 1, 3, 2) and check if its equal to its reverse. Zero thinking required
Doesn't quite work. In your example [2,3,1,3,2], the tree isn't symmetrical, because after the root, a symmetric tree will always have an even number of items on each level- so your reverse check will pass even though the tree isn't symmetrical.
Also, if say at level 2 (where root is level 0), you have no children on the right, and two children on the left- but both children are 3. Then you would have [3,3], which passes the reversal test even though the tree isn't symmetrical.
There are ways to handle all these cases, but it will get messy fast.
What if it's a skew tree
@@gvenkatesh8935 then its automatically not symmetric
@@siripiripiri1 what about the time complexity
If you've done a few tree problems and know recursion this is very easy
Good video man love the problem choices
Glad to hear it!
Are you doing the full comparison two times? That is, when root1==root2==root, you execute sym(root1.left, root2.right) that verify all the tree but, you are also doing sym(root1.right, root2.left) that repeats all the comparison a second time. I think you should include before the las line of the function: if root1==root2: return sym(root1.left, root2.right) isn´t it?
But what matters is not the solution, rather how you come up with the solution on your own…
which is irrelevant when the question is an extremely popular leetcode challenge. that's why you'd hope it wouldn't show up in interviews!
Understanding how to solve this basic recursion problem so that you can solve harder ones is irrelevant?
@@zaringers to be clear I mean for this one specific question, sorry. As in, if an interviewer asked you this question then it would nearly be moot because you could have memorised an explanation. But like you say this could still be applied to a more challenging or unique problem
@GregHogg - While constructing the tuple why did you use sorted( 4 numbers)?
Does the problem description say such ordering constraint?
So good!!
That will run twice, though
Recursive function
Understanding data structures and algorithms conceptually can be straightforward, yet unfamiliar syntax may lead to overly complex implementations.
I think this is the reason why people find some “easy” problems complicated and difficult, at least that’s the case for me.
"Easy"
It was an interesting exercise on one of the courses taught in college, It was fun to do it in C. Now I forgot how to do it quickly.
Easy to understand and even make a diagram but very difficult to type the code
very elegant
agree with you, `easy to understand` :)))
Amazing
great
Problem in a short video!
That's way behind brilliant
for some reason i just dont get recursion... i mean i get the general concept, but it feels like there's a mental block for me that stops me from actually creating any recursive solutions... if someone else ever got over that do lemme know how, it'd help a lot... i think its a pretty cool thing and i hate not being able to do it
I generally only use recursive if there are multiple paths, you can use looping but it can be annoying. Imo recursive is easier to read at the cost of performance however the impact varies. My advice write the code as a loop, if it works, improve it (if possible), then look to recursion. Look for tree and graph questions to look into recursion as they often have branching paths, not all solutions require recursion. Don't worry about not being able to do it, you'll often find recursive questions like Fibonacci or factorial are meant as introduction but are just significantly simpler and easier as a loop. You might actually already be doing it in the most efficient way.
thanks for sharing your insights. i'm not a newbie btw, i have a job n everything... and i never needed a recursive solution... ever.. so that makes it even more weird ...@@Bargi3
This might sound like a cop-out, but I've experienced the same as you're describing rn. It just clicked eventually. Just keep on learning. :)
Try to understand recursive function by writing all the function calls on pen and paper on multiple problems recursion will be easy
If you really care about understanding recursion, try to pick up a functional language like Haskell. It will force you to get good at it.
whats sym(root, root) for
I got this question on a computer science test
Whenever I try to use recursion in leetcode I get a timeout error :-/
You've earned by subscription ❤🥰
Yay, thanks a ton! 🥰
why root val should be false? i don't get it
While this recursive looks smoother to eyes. It might be difficult to come up with the approach if not solved before. Also, it’s slow and consumes a lot of extra space that’s not needed. How about this?
var isSymmetric = function(root) {
var q = [root];
while(q.length){
var l=0, r=q.length-1;
while(l
that was the first solution that came up to my mind. How can you solve this differently? It's a natural comparing process from the real life, is it not?
now do it iteratively
I would have expected a harder question for such companies
Yeah they probably would ask something harder in today's competitive market
How about bfs solution.. push child nodes in queue as well as insert in array, left & right pointer to compare elements in array.
Absolutely you could do that :)
people saying this is unintuitive really need to study more or just see recursion more often. this is the most basic solution logically and can probably be reduced to like 5 lines (depending on your language perhaps).
this probably isn't even the best solution. my expectation was that this would be the obvious solution that the interviewer is expecting but probably wouldn't get many points for. i feel like there is probably a more efficient algorithm that is iterative rather than recursive
You could always use a stack in place of the call stack for DFS but I feel the recursive one is really elegant
Well, there is a mistake, a tree formed with only one branch on each side is a mirror of itself, but in your algorithm it would return false
Very cool!
How about doing level order traversal and checking if each level is symmetric or not. I think that will work too
For sure you could do that :)
@@GregHogg Hey Greg, thanks for confirming. I appreciate that !
You will never need this level of logic on a daily basis
If you're doing coding interviews, it could be a lifesaver
I disagree. The principle is very useful. Recognizing the way the recursive solution is discovered is why it is taught in formalized education.
I would consider hiring someone who did this without using recursion. Recursion has no place in production code.
what site is this from where youtubers take these questions?
Leetcode😊
left DFS and right DFS comparison
Yes!
In elementary this is called factorial tree
Interesting
@@GregHogg At least here in Indonesia there is 2 branch in solving this factorial tree one is smallest common multiple and Greatest Common factor
This is not easy, the solution looks easy and straight forward, but coming up with the solution is tricky
Why do we call like this?
To iterate over the left and right side of tree and match them
There's only 1 root thou...😅
I think we need a better algorithm because I think this runs at 2^n speed. 🙃
Yeah it's definitely not exponential lol
My bad I was using too small of a number to see the limit for this...
it's O(4(n + c))
|
| - |
|| - ||
XX XX - XX XX
List of steps we check "if not root1 and not roo2"
1 root, root
2 root.left, root.right
3 root.left.left, root.right.right
4 root.left.left.left, root.right.right.right
5 root.left.left.right, root.right.right.left
6 root.left.right, root.right.left
7 root.left.right.left, root.right.left.right
8 root.left.right.right, root.right.left.left
9 root.right, root.left
10 root.right.left, root.left.right
11 root.right.left.left, root.left.right.right
12 root.right.left.right, root.left.right.left
13 root.right.right, root.left.left
14 root.right.right.left, root.left.left.right
15 root.right.right.right, root.left.left.left
16 root.right, root.left
17 root.right.left, root.left.right
18 root.right.left.left, root.left.right.right
19 root.right.left.right, root.left.right.left
20 root.right.right, root.left.left
21 root.right.right.left, root.left.left.right
22 root.right.right.right, root.left.left.left
23 root.left, root.right
24 root.left.left, root.right.right
25 root.left.left.left, root.right.right.right
26 root.left.left.right, root.right.right.left
27 root.left.right, root.right.left
28 root.left.right.left, root.right.left.right
29 root.left.right.right, root.right.left.left
Let's improve it just a little by changing 1 line.
`return sym(root, root)`
to
`return sym(root.left, root.right)`
if we need to add a check for if root exists, run that check before defining the internal sym method to meet the edge cases.
29 steps is still a bit extreme for only 7 nodes (1 of which we don't ever need to check as if it does or doesn't exist, has no impact on if it's square
No comp science student should have to prepare for this Kind of questions.
Shut up
and no comp science student should solve it with recursion :D
What about non-binary trees? *badum tss*
that wasn’t part of the problem
now i wonder if they accept the unholy abomination that is recursive functions or if they'll have you rewrite it as a loop :D
??? Are you a child? Recursions are completely normal
Iterative code for this task would be several times as long / as complicated
@@ink2467 Considering your immature reply to a joke if anyone's the child it is you, putting that aside.
Recursions can make sense but often times programmers jump to the recursive solution despite there being an iterative one which is basically always more efficient due to the underlying mechanics of recursions unless the compiler fixes it for you. So if this question isn't followed up with a more abstract one regarding the issues that often plague recursion it's a bad question.
@@ink2467 Besides depending on the tree structure used getting an in order list is going to be trivial, then cut it in half flip one (or just count from the back, whatever is supported in the language you use) and you've got the iterative solution not really difficult just takes ever so slightly more thinking.
@@ink2467If the tree is big, recursion can cause stack overflow. A loop would work with trees tens of thousands time bigger (until you runs out of memory).
after watching about 4 of these videos i have concluded i am no where near good enough to work at a faang company
it wont work
Whyyyy it seems soo easyyy, however, I always face errors problems
That's how it goes haha
@@GregHogg I actually find you videos way educative, I learnt a lot of stuff, thank you
Say waaaaaaaaa
Waaaaaaaaa
Minus one point for bad function names
First half is easy, the second half, not so much
Are you sure this code will take an adequate amount of time to run? It's a quadruple recursion.
no, it's a binary recursion. Inside of the sym function you only call sym twice. The fact that each call has two parameters is meaningless in terms of quantifying the degree of recursion.
Also, you only visit each node once. This should run in O(n) time where n is the number of nodes in the tree, and O(logn) space. The space complexity is due to the fact that it's depth-first, so you'll only ever have a function call tower of at most the height of the tree.
How is this easy 😂. It should be medium already
You were probably breaking it down to make it more clear, but you could probably shorten that to a one liner. I'm not sure about python, but here's my Java implementation:
private static boolean isSymetric(Node l, Node r) {
return l == null && r == null || l.v == r.v && isSymetric(l.l, r.r) && isSymetric(l.r, r.l);
}
Why is this easier to understand
Shorter!=Better
Never said it was.@@tkorful
@@tkorful However in this case I'd argue it is faster because his version has a bunch of if statements and that can cause branch predictions by the processor. If those predictions are wrong, you lose efficiency and processing cycles. I'm not sure about Python, but some compilers are smart enough to notice things like that and automatically optimize out those if statements, but if you do it yourself, it's even more assured.
a face for radio, and a voice for print. my condolences. this guy is a tool and he often doesn't know what he's talking about. guys/gals, if you're grinding leetcode, you're going to be disappointed in the long run. real long term success in software engineering is dependent upon your ability to be a clear communicator and an analytical thinker, not memorize solutions.
You're a nice guy. /s
@@AtacamaHumanoid fuck being nice, and fuck the loser OP
Me and some friends really want to create one AI and we really need your help if you're interested tell in the other social media invitation.
Me and some friends really want to create one AI and we really need your help if you're interested tell in the other social media invitation
and basically useless
If you're being asked an algorithmic question during a job interview, you know you're one of the lower plebs. I have not been asked a single programming question for any job or project in the last 15 years, and I make 300k a year.
That's not true, at least in the US. FAANG will ask LeetCode style question to people with 20+ YOE for roles that pay 700k+. Of course they also have behavioral and system design questions, but LeetCode does not go away.
And your function is very slow… if you look at the assembly instructions it takes… pop pop push pop push🫷