Data Structures: Binary Search Tree

Key Takeaways

hi I'm Gail lock McDow author of cracking coding interview today we're going to talk about detecting if a tree is actually a valid binary search tree a binary search tree as you may recall is a binary tree so has a left node and right node but it's one where all the nodes on the left for given node all the nodes on its left are smaller than it and all the nodes on its right are bigger than it so we want to check to make sure binary tree is actually binary search tree and so that means checking to make sure that ordering property is true so one approach that a lot of people take that is actually mistaken is they think okay I'll just walk through my tree and check to make sure for any given node compare it to the left node compare it to the right node and see if it's in the right order so is the left node smaller than the current node and smaller than right and the problem with that is that even if that's true it may not be a valid binary search tree because there could be something something else underneath it that's bigger than the parent so for any given route maybe it's grandchild is actually bigger than it and maybe it's the left grandchild is actually bigger than it so that won't actually work another approach that is correct but slow is we can say okay all the nodes on the left must be smaller than all the nodes on the right so take each node get the biggest node on the left compar it to the to this node get the smallest node on the right compared to that node that'll work but it's pretty inefficient these get min and get Max operations uh require walking through that whole tree so so that's going to actually get very very slow a faster way is we can flip around this logic we can say okay at the very beginning our root is valid we have no the root can be anything in the entire world but when we go to the left we going to walk through all its children and when we go to the left everything on the left has to be between the integer minimum and the root value and everything on the right has to be between the root value and integer maximum okay so now let's go to the left well that you know we'll check to make sure hey is that is that node on the left is that within those values great it is okay keep going now when going go to the right side of that all those values must be between that left nod's value and that root nodes value so we're going to pass around these these ranges of Min and Max and say at every any given point are you within that Min and max range so that's how we tackled this problem okay so what we need for this method actually is we need check BST to take in a Min and max value and this initial node is going to just take in pass an integer Min so initially the root can be any value at all at all actually now I'm going to make sure I'm going to specify here these are inclusive ranges okay so in the very beginning first I want to do so I want to check to make sure my root is in the right value so if it's smaller than my Min or it's bigger than my Max return false um I also want to be careful of I need a base case here so if root is null then return true otherwise go left or right so check my left and right root dot um do left and I'm going to come back to what these ranges are in a second so check the left and check the right if both are valid then it's valid okay that's a basic log now initially my so my root can be any between Min and Max if I go to the left of my root anything down there can still be as small as the Min but it cannot be any bigger than the than the root and in fact it can't even be equal to the root because we actually do not have duplicates in this tree and so the biggest so my values on the left of my root can be anywhere between Min at the smallest and one smaller than the root when I go to the right things can be at least or they have to be at least as big as root actually one bigger and they can be up to that max value now let's run this and see what happens perfect it worked so we can do it so in more test cases if we want but let's remember let's walk through what this does so this basically flips around our initial logic what we're going to do is pass these ever shrinking Min and Max values so the iic is basically root had had to be somewhere between Min and Max if we go to the left we've now shrunken the biggest those values can be they can be between that old minimum and root if we go to the right then they can be still as big as that Max but they can't but they have to be at least as big as root now you want to be very careful on uh any recursive problems to you know pay extra close attention there to the base cases because that's a really really easy thing to mix up one thing I always check for in a recursive problem is if I'm returning a Boolean I definitely want to make sure that I have some sort of return true and some sort of return false statement somewhere because if obviously if I only have a return false statement how would I ever get anything other than false so that's just a quick little sanity check to do okay right so that's that's how we tackle this problem the efficiency of this problem this solution is actually really nice we actually have a linear time solution and we know since we have to touch every single node in the tree we can't do any better than that so this is pretty pretty close to as optimal as we can get and the space complexity by the way of this problem is going to be if it's a balance tree it's going to be log n because of that recursive complexity so now that you've you seen this problem why don't you try either try this again on your own or check out some new binary sech tree problems good luck