Pseudo-Palindromic Paths in a Binary Tree - Leetcode 1457 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem pseudo palindromic paths in a binary tree we're given a binary tree where the values are only going to be in the range from 1 to 9 and in this problem we care about the paths in the binary tree that go from The Root Down to the leaf nodes we want every single one of those such pths that's one this is another one and lastly this is one as well so there's three paths right and that's because there are three leaf nodes of course now for each of those paths we want to first get the path itself so like one path going down to here is 233 another path going down to this node is 231 the last one going here is 211 the order of these values actually doesn't matter we don't care if this itself is a palindrome we care if we can take these digits and somehow arrange it such that it looks like a palindrome so right now this isn't a palindrome but we know we can rearrange it to 3 2 3 that looks like a palindrome to me and if you don't know what a pal drum is basically it means if you're going from left to right or right to left it's the same so 3 2 3 reads the same from front to back and back to front that seems kind of difficult doesn't it to take these and just somehow know whether we can create a palindrome from it or not like do we want to rearrange it in every single possibility that can't possibly be efficient and it's not going to be super easy to code up either so that's kind of the hint in this problem that there is a better way to do it we don't want to get every single permutation of every single uh Leaf path so how can we do it well let's learn a bit about palindromes for a second what kinds of palindromes are there well there are odd length palindromes we just looked at one 3 2 3 there are also even length palindromes like 3 2 2 3 why is it that we can have palindromes of odd length as well as of even length try to figure it out because look at this guy over here if I get rid of these threes it's still a palindrome like let's think about the base case we just have a single two that's a palindrome look at the other case we have two values they're both two but it's still a palindrome but now if we try to roduce like a three over here 23 that's not a pal Drome why is that why is it not a pal Drome why is 23 four also not a paland Drome try to think about it the pattern here is that we can only have one digit that occurs an odd number of times in other words if we were to take any such string any possible string and for every single digit we want to map it to the count of that digit and we must ensure that only at most one digit occurs an odd number of times so if we have this mapping we can then get the number of digits that occur an odd number of times that'll just be an integer so in this uh string down here this is getting kind of messy so let me kind of clean it up a little bit in this string we have three it occurs two times we have two it occurs once that's an odd number of times so we have how many numbers occurring an odd number of times just one so this is a palindrome what about the second string it looks like every one of these occurs once that means we have three numbers that occur an odd number of times this is not a palindrome so let's look at the next one occurs once this occurs twice so we have one number that occurs an odd number of times so this is again a palindrome so we have two palindromes because we have two such paths that have less than or equal to one number that occurs an odd number of times even just saying that out loud is kind of difficult but I hope that this idea makes sense that's kind of the Crux of this problem once we know that we've handled the pal drone part now it's kind of the easier part like how do we get every single path down to every single leaf node we can do a very simple in order traversal and the best part about that is we don't even visit multiple nodes twice because we'll go down here pop back up then go down here then pop back up and then go down here we're not processing a node multiple times therefore the time complexity in this problem is going to be Big O of n you might think the hashmap is going to increase the memory complexity it really doesn't because remember we only have nine digits the hash map isn't going to be very large but there is something that does affect the memory complexity the fact that we're going to be using recursion to Traverse this tree means we might have a call stack that is as large as the height of this tree therefore the memory complexity is going to be Big O of the height and in the worst case the height might be equal to the number of nodes so you can either say it's this or you could say it's Big O N in the worst absolute case okay now let's code it up okay so the first thing I want to do is declare a hash map so I'm going to create a hash map just like this I'm going to call it count and I'm actually going to use a default dictionary because it's just a bit easier it's going to be default dictionary of integer this means that like if I were to do something like this count of let's say five or six and then add one to it we'd get an error because what this is doing is this and this will give us a key does not exist error but with a default dict this will return zero by default even if the key doesn't exist and that just makes things a little bit easier it removes the need for us to do an extra if statement the other thing I'm going to do is have a variable which will tell us the number of digits with an odd count okay with that out of the way let's start with the recursion let's do our in order traversal or DFS I guess I'll just call it DFS because it's a bit shorter and we'll pass in the current node and ultimately we want to call our DFS on the rout and then return the result okay now the simple base case is always if not Cur let's return zero we have an empty tree and that's how I'm going to handle it though I will say there are probably multiple valid ways to handle the base cases for this problem now if the node is not not null then let's get the count let's get the value of the node and then increment the count so let's say current. Val let's add one to it okay now this part I didn't actually talk about in the drawing explanation but how do we want to manage this odd I kind of talked about it like we're going to create the entire path then we're going to read all the values at the end count them and that will tell us what the odd count is but we can actually compute this as we go we don't need to maintain all the nodes in the current pth path that we are on we can do something kind of clever if now after incrementing the count of this value if now it is an odd number we should probably increment odd right we have one new number now that is odd now in the opposite case what if we had an odd number like what if we counted some value has an count of one it occurs one time therefore it occurs an odd number of times but now we see that same number again now we have a count of two for that number now it occurs an even number of times therefore in this case we should probably decrement the count of odd right this is probably the most confusing part of the problem but think about it draw it out and I guess just to walk through it on the left side over here when we have this two we have two occurs one time it occurs an odd number of times when we have this three it occurs once it occurs an odd number of times so at this point we would have incremented odd twice now when we get to the last Leaf node three three occurs twice so this time we actually decrement odd it's going to be equal to one now and that makes sense because when you look at the path we have one number two which occurs an odd number of times long story short what we can do is say that the change in odd is going to be this it's going to be one if the count of that value is odd in other words if it's equal to one other we're going to decrement odd we're going to set the odd change to Nega one using that odd change what we're going to do is update odd now you might be wondering why did I create this extra variable why didn't I just put odd over here and then have the plus equal set to this because think about this going back to the tree here on the left once we're down here at the bottom three three occurs two times when we pop back up we're going to do the opposite of what we just did if we incremented the odd count by one now we have to decrement it by one cuz we lost that three if we did the opposite if we decremented the count when we went here when we pop back up we have to increment it so basically what I'm saying is that before we end up returning down here to odd we have to make sure that we subtract the odd change before we do that and don't worry like in between these there is going to be recursion that's the whole point of this cuz clearly we're just canceling this out and that would be meaningless if there wasn't anything in between this now we're ready for the interesting part there are two cases at this point we might have actually reached a leaf node cerr might be a leaf node how do we know if that's the case if not c. left and not c. right it doesn't have any children what do we do in that case we're definitely going to end up returning something we're going to return the result what is that result going to be well like we said if odd is less than or equal to one then we return one otherwise we can return zero cuz then we don't have a path so this is what I'm going to do I'm going to use a tary operator here I'm going to say the result is equal to one if the count of odd is less than or equal to one otherwise it's equal to zero and this is what we're going to return but I did this for a reason we're going to put something in between here because like I said we want to make sure we change odd we want to update odd before we return and just like we want to update the count of odd we want to update the count of the number number as well when we found C we incremented the count of C by one when we returned from here we want to decrement the count of Cur by one so let's do that right here okay so that's the leaf node case that's the other base case finally for the recursive case we can say the result is going to be equal to the sum of whatever the result is in the left sub tree plus the right sub tree and it looks like I didn't even need paren es here because this line isn't too long and I also realize it's not in order it's actually DFS so it's even shorter and so from here we'd also want to return the result but don't forget we probably want these two lines down here as well and since we're duplicating these lines maybe we can refactor this a little bit to have an else statement over here and put this result inside of the whoops put this result inside of the if statement well the else block and we want this to occur regardless we want to return the result regardless so let's just take these three lines of code out of here and they will execute down here anyway so we did a little bit of refactoring shortened up the code we are nearly done there's one last thing that I saved for the end when you have an object like count declared outside of a function like this we can access that and we can modify that object when I say modify like we can add values to it remove values but we can't reassign it if I were to do this count is actually equal to this I would get an error actually forget that we can reassign it and we can actually do the same thing with odd like if we wanted to reassign odd to something if we wanted to assign it to a 10 for example this would actually work what won't work is this odd is equal to odd + 10 because what this tells python is you've declared some variable called odd in the scope of this function it tells python that you're not using odd from outside you're actually declaring a new version of odd and then we're accessing odd at the same time like how can we say odd is equal to odd + 10 when this isn't even assigned yet it will give an error and let me just run this to prove it see the error we get is cannot access local variable when it is not associated with a value so the way to fix that is just to declare Odd as a nonlocal value so just like up above this will basically tell python that we're actually not declaring a new odd value down here we're actually using the odd from out here that's the entire code let's run it to make sure that it works as you can see on the left yes it does and it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon