Insert into a Binary Search Tree - Leetcode 701 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem insert into a binary search tree we're given the root of a binary search tree and a value that we want to insert into the tree and then we want to return the new root of the tree also it is guaranteed that the new value does not exist in the original BST and they also clarify that there are multiple ways to solve this problem there's multiple ways to insert into a binary search tree and we can return any of them thankfully now before we get started on the solution let's actually break this problem down there's a few key points to notice first of all this is a binary search tree not just a regular binary tree so there is a sorted property to the tree remember that for every single node in the tree every node in the left subtree of that node is going to be less than the value here four it's going to be less than 4 and every value in the right subtree is going to be greater than 4 and this property is recursive so it's not just true for the root node it's true for every single node in the tree now they also clarified that we're guaranteed that the new value that we're inserting in this case 5 does not already exist in the tree that's very important because that's first of all usually the case with binary search trees but it's also important because we need to find a position that we can insert this five in now technically if we wanted to we could put the 5 in the root spot and then like rebalance the entire tree around the new root value that's kind of a difficult way to do this now the simple way to do this you might already remember if you took a data structures and algorithms class but I really want to emphasize the thought process behind this problem because it's very trivial for me to solve it because I kind of know exactly how to do it the easiest way you start at the root and you basically keep searching until we get to a null position now how do you search while you use the sorted proper if we're inserting a 5 is that greater than four or less than four we know it's definitely not going to be equal to any node in the entire tree it's never going to happen we're either going to go to the right or we're going to go to the left in this case 5 is greater we're going to go to the right now for 7 are we going to the left or are we going to the right we're going to go to the left and now we reached a null position we're guaranteed to reach a null position because like I said we know for sure 5 does not already exist in the tree so every time we get to a new node we're either going to go left or we're going to go right now unless the tree is infinitely large we know for sure we're going to reach a null position and that's where we want to insert this 5 into so we put the 5 over here and you can see that's pretty much what they had in the output now how do we actually code this up well there's two ways to do it we can do it the iterative way or we can do it the recursive way let's compare and contrast these two different ways to do this very quickly if we do this iteratively we're going to start at the root and then we're going to go to seven and then we're going to end up at a null position now how do we actually insert a node here well we would want to connect this node and add a left child for it a five so therefore we don't really want our pointer to end over here because we need access to the parent node so we would want to stop at the point where we see that okay we want to go left but left is null so therefore we stop and we go ahead and insert the node that's a pretty easy and doable way to do this we could also do it the recursive way which I think is a little bit trickier because there's a very important Edge case here that I want to emphasize what happens if we have an empty tree we want to insert five into an empty tree because remember we actually have to return the root of the node of the binary search tree and in this case we'll have a new root node if our tree is empty then we have a new root node so in the iterative solution I think it's pretty easy because all you have to do is create a node and then return it but for the recursive solution it's a bit different because for the recursive solution we're actually handling that edge case that I talked about in both cases because in the recursive solution when we get to the null position over here we actually want to create that node 5 and then return it up to its parent and then from its parent we're going to say we inserted a new node into the left subtree and then we return to that tree so we're going to take that tree and set it to the left child of seven I think the recursive solution is a bit harder but I think it's also more powerful because you can apply it to other problems more easily and I think it's really important to understand so I'm going to be focusing on the recursive solution when we code it up right now but I'll also briefly show the iterative solution towards the end before we move on what would be the time complexity of inserting a node well first of all how are we going to measure it we can measure it based on the size of our binary search tree let's say n is the number of nodes in our tree and we could also measure it using the height of the tree let's say h is the height of our tree technically in the worst case this is going to be the time complexity Big O of H because we don't have to visit every single node we're going to every step either go left or go right so we're just going to basically have like a chain like this which is going to be the length of the height of the tree in the worst case though we might not have a balanced tree it might just look something like this technically the worst case time complexity could also be Big O of N I like to say Big O of H though because it's more accurate I think because H could be equal to N I think it's more correct to say that the time complexity is the height of the tree it's also worth mentioning though that the recursive solution takes extra memory because we have a call stack we're going to do it recursively we're going to call a function here we're going to call a function here we're going to keep doing that basically same thing the height of the tree so the memory complexity is going to be a big O of H whereas if we do it iteratively we don't have a call stack we just have a pointer that we keep shifting and therefore the memory complexity of that will be constant Big O of one okay now let's code it up remember the first Edge case what if we have an empty tree well then we basically want to create a new tree node we can do that with the Constructor passing in the value parameter that we're given and this is what we want to return after we've created a new tree otherwise we know we have to keep searching until we do reach null we know we're going to reach it eventually but we have to figure out which direction we want to go in is the value greater than the current value that we're at the current node that we were given if it is then we want to call insert on the right subtree passing in the exact same value of course now here's where things can get a bit confusing remember after we insert into the right sub tree what if the right subtree of the root is null that means what this insert function would do is it would just create a new tree node and then return it but if we return it like this we're not doing anything with it then root Dot right will still equal null so to change that we want root dot right to be equal to the new node that we just inserted and we want to do the exact same thing in the opposite case where our value would be less than root dot val I don't have to specify that here though because we know for sure value is never going to be equal to root dot val so I'm just going to copy and paste this and just change a couple values we want to do this now on the left side of the tree because our value is less than the current root value that we're at so we basically just change this now the last thing here is after we do that we still need to return the root the reason being what if root dot right here when we pass it in to the insert function is non-null then we would basically call insert end up in this function and then maybe we'd have to call insert again going either of the directions and keep doing that multiple times so in that case the root actually would not change the route that this insert function would call would not change we would want to return it and then keep assigning it to root dot right that would not do anything in that case where it's not changing but we know we still have to have these assignments in the case that the return value did change which would of course only happen if the route that we passed was null and then we created a new node and then returned that so let's run this to make sure that it works and as you can see yes it does and it's pretty efficient now let me briefly show you the iterative solution so this is the iterative solution we have the same base case if we are given an empty tree we just create a node and then return it otherwise we set our current Warner equal to the root and I just go while true because we know we're going to keep going until we reach null and the way I wrote this we never need to break out of this while loop because I'm just returning root inside of these but you know you could have done it the other way that's up to your preference but logically this is mostly the same if the value we want to insert is greater than the current value we go to the right otherwise we go to the left now what happens if we can't go any further to the right then we go ahead and insert the new node because we know we found the null pointer and then we return the root notice how what I'm returning is not Cur I'm returning the root because that's what we want to return for this insertion otherwise though if we didn't find the null pointer then we go ahead and just say Cur is equal to Cur dot right we're doing logically the exact same thing on the left side of the tree as you can see below and that's pretty much the iterative solution I'll go ahead and run it to make sure that it works and as you can see yes it does and it's pretty much just as efficient in terms of memory it's probably a bit more efficient if this was helpful please like And subscribe if you'd like to see code solutions for languages other than python check out neat code.io it's got a ton of free resources to help you prepare for coding interviews thanks for watching and hopefully I'll see you pretty soon