Insert into a Binary Search Tree - Leetcode 701 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:58 - Coding Explanation

leetcode 701

#neetcode #leetcode #python

[mightyshenanigans]

My man be running on beast mode with the uploads to this channel 🔥

[doc]

This is one of the first leetcode solutions I did pretty much all on my own (I had to check to be sure but I actually had the entire code before checking). I'm going through Neetcodes DSA course and my coding skills are getting really good.

[WaldoTheWombat]

Here's the solution with some clarifying what's going on:


class Solution:

def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
"""
This is a recursion function, so in each recursion call the root is only the root of the subtree.
"""
if root is None:# if current node is None, in other words, if we've reached all the way down the tree (eventually we always reach all the way down), then create a new node for the new value and reutrn it to the previous call, which will set it in either the left or the right of its subroot.
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root # This is the return statement of all the other recursion calls. They only execute (backtrack) after we've already reached the bottom of the tree and created the new node. What we're returning is
# the root of the current subtree and we're actually always returning the same root that has already been there. So what's the point?
# Well, it's just a way to implement this backtracking solution without also writing a helper function.

[WaldoTheWombat]

Here's a non recursive solution:

class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None:
return TreeNode(val)
current_node = root
while True:
if val < current_node.val:
if current_node.left is None:
current_node.left = TreeNode(val)
return root
else:
current_node = current_node.left
else:
if current_node.right is None:
current_node.right = TreeNode(val)
return root
else:
current_node = current_node.right

You could avoid the null check at the beginning by asking while(cur) and returning TreeNode(val) after the loop. I don't know if while(True) is cheaper than checking an actual variable

[georios]

I like how you explained the pros and cons of using the recursive solution or the iterative

[CS_nb]

this is a really good explanation of recursive tree problems in general