Test If A Binary Tree Is Symmetric ("Symmetric Tree" on Leetcode)

[Music] all right so it's good to be back we had a good two days off I could not find a place with a whiteboard that was open because it was Christmas and I don't know I'm crazy and I want to do this problem but it is exciting to be back and we have a very cool problem today well I mean cool in the sense that we do these problems to continue to sustain our livelihoods and these are actually kind of boring but test if a binary tree is symmetric so the question is we need to test if a binary tree is symmetrical in its structure and symmetrical in value so if we draw a line down the middle of our tree down straight through the root vertical line will the tree fold on itself and will the values be equivalent so here are examples if we have no that is basically an equivalent tree I mean it is just no but if the root is null of our binary tree then it's symmetrical there's nothing to compare if we just have one node if we draw a line straight through it's still symmetrical and we have a tree like this or root is one we have two and two if we draw a line straight through do you see how they'll fold on each other and those twos are the same and is structurally equivalent and if it's going to have value equivalence it must be structurally equivalent here is an example where things go wrong we see one it's left value is two and his right value is no this is where if we fold the tree on itself we're not going to have equivalent values and just to further this do see it stays symmetrical this stays as a root of two left and right one it stays symmetrical here but where do we fail we stay symmetrical here but right there if we draw a line everything will fold over and work except for the four and the null right there so those will not match for does not will know they're structurally different this is not even a value difference we could put a five there if we put a five there it still fails why because values are not the same these values are not the same if we fold them these are the two values that fold onto each other and they need to be the same and they're not this is why this tree fails so this is the problem test if a binary tree is symmetric a lot of people asked normally when we deal with trees it's recursive but a lot of people have problems were thinking how do I traverse a tree how does this recursion pan out and let me give you an example to show you how you need to think about this problem so that you understand how the recursion and traversal will happen all right so forget about trees forget about recursion forget that okay we're in an interview high-pressure situation let's go back to what we were doing I give you an array tell me if this array is symmetric if we put a cut through the middle if we put a cut through here tell me if this array is symmetric this is kind of like checking if a string is a palindrome so what are you gonna do you're going your eyes your eyes are gonna go here what what are you doing what what are we doing fundamentally we're doing a pair comparison we're comparing pairs are those equivalent yes what's the next pair we go one more inward what's the next pair and then what do we see for design equal three this is not a symmetric array so now what you've establish is you've put that aside it's a tree we need to find symmetric the whether symmetric you put that aside and you get back to what am I really trying to solve what are my points of interest and in recursion every single recursive recursive thing is going to take in points of interest and our points of interest are two values we're going to be doing pair comparisons this is huge because when we're working with the recursion the way we crafted the signature of our recursive function is going to be based on what we're trying to solve what we're interested in we see that we're going to be interested in pair comparison so our recursive function is most certainly at the least going to take in pairs of values so now let's get back to the binary tree and see what pairs we need to compare all right so here let's color code everything here's our example that we were working well a little different from what we were working with before and remember pair comparisons now we're thinking forget the code do this in your head do this by and like how are you going to do this so first off we know the route no matter what a route is symmetric by itself we don't even need to think about peer comparison in a recursive function we could pass the route as both of the two two items being compared because it's going to compare it to itself and it's symmetric so what do we need to compare next let's change color next we know we need to fold these two guys together okay those need to be equivalent but then where do we go from there this is the key thing that's going to craft our function for us so what we need to do is let's this is the left subtree this is the right subtree so this is a left subtree this is a right subtree so the theme the the left value this guy who does he need to be equal to B needs to be equal to him so what does that say fine yeah am I too loud so notice okay it's tough to write recursive functions but let's not even look at the code we haven't even got to code yet what we notice is our left subtree and right subtree we're working with these nodes representing the root of those sub trees we notice the left sub trees left must equal the right sub trees right this is part one now what else do we see we also see that this guy needs to equal this guy so what does that mean that must equal that well what is that let's write another rule well here's rule one here's Rule two so what we need what we need to happen is we need the left subtree so left to equal the right subtrees right we need the left sub trees right to equal the right sub trees left we see that doesn't happen here so this first thing passes but this does not happen think about this this is this is the answer this is what needs to happen this is how the traversal needs to happen our recursive function will take a left subtree and a right subtree it's going to enforce these rules if these rules fail at any point in our traversal it's over the tree is not symmetric if it fails here then we're gonna bubble up the answer that it failed is false so for this guy for this guy he's gonna say is my left and right symmetric he's necessay is my left or right symmetric so let's get into the recursive code and see how the code pants out that now that we've deduced these rules okay all right so here oh all right so here is everything converted to the code nothing has changed all we're doing is converting this to logic everything that we just explained is what we're about to do if the root is null immediately we short-circuit execution we're finished it's a symmetric tree we're done but what we do is if it's not not then we need to go into our recursion and we need to check the left subtree and the right subtree remember back to what we just did okay so now we go into here if the left subtree and right subtree if our nodes are no they are symmetric they are non-existent and we fold correctly to both non-existent positions we return true the check passes for those two subtrees but if they're both not know if they're both not know that we need to check the value and then we need to continue our recursion to the left and rights of the node we are sitting at and we need to continue to check cemetary first we check their values if their values are the same good we're done with these nodes we're holding and then what we need to do is we need to check to make sure that our left sub trees left it's equivalent to our right subtrees right and that our left sub trees right it's equivalent to our right subtrees left so as you can see here left left sub trees left needs to be equal to right subtrees right left sub trees right needs to be equivalent to the right sub trees left so we enforce that we continue our recursion and we return we will bubble up the answer let me save return in a recursive we didn't return our recursive call we know that whatever that recursion will return to us will bubble back up the call stack and return our answer to our top level caller and then finally we return false when would we reach this line first we know that both the nodes are no then we know both those aren't know if one node has a value and one node is no or this note if the left subtree has a value and the right subtree is a null or the right subtree has a value and left subtree is null then we it's impossible to have symmetry because they are structurally different we can not even do a value check and therefore we return false so this is our policy this is our never we define a recursion function to operate on a tree it's as if we're defining a policy that we must enforce through our recursion and through our iteration through the tree so this is gonna bubble its way down it's gonna go down the tree come back up gonna go like that do it's like searching and and go down the tree and do its checks so what would the time and space complexity be so let's really think think about this the time is kind of easy because it's a word I need to check and nodes and we're did check if the tree is symmetric we must check all of the nodes we have n nodes we declare the number of nodes as n so we have all of n time and the time complexity our space complexity why is it all of H or height but during our recursion we are only going to keep up to the height of the tree our call stack is only going to have as many calls as as tall as the tree so when we're going down we're gonna do go like this we're gonna go like this like this or art art the the amount of space we use on the call stack is not proportional to the amount of nodes is proportional to the height of the tree because we're doing a height traversal it doesn't work out exactly to the height but it is proportional to the height and it scales with the height as our input gets large so we're gonna see this in different problems with the space being all of H so it's going to become more familiar with you as we do more problems but could the space be at all of n you know if it's a skew tree could it be where space of n because yes the call stack couldn't go that deep but think about this if if we had a skewed tree it would immediately fail if our tree was skewed like this and we did a comparison like that we would fail on the first comparison it wouldn't really make sense to say that the worst case would be oh well it wouldn't make sense but we would instantly fail our comparisons so in a problem like this why would you even get a skewed tree so if it's o of H is like the more common like it makes a lot more sense than saying o of N worst case because that probably would not even happen it would fail on the first comparison so this is the problem we just walk through how you think about the recursion do not the thing about recursive functions best way to get the signature of your function is to think about what is my policy what must I enforce what do I need to know through every single iteration of this recursion what is each frame need in this problem we need two nodes we we didn't know which nodes initially but we knew we needed to compare pairs we knew we needed compare pairs of something in this problem that turned out to be pairs of sub trees in other problems it could be anything else if we're doing backtracking and it's like the end Queens problem or something maybe we're we need to keep the data of how many placements we've done so it all depends on what your function needs and the more problems you do the more you improve in this so this is this problem if you liked this video hit the like button subscribe to the channel we're trying to do a video every day to improve engineers and the whole point is channel is to empower the software engineer to perform better in the interview know what to expect and perform at their best and that's what this is all about so yeah [Music]