Insert into a Binary Search Tree - Leetcode 701 - Python

[@NeetCodeIO]

If you're looking for today's daily LC problem, I already have a video on it here 👉 kzbin.info/www/bejne/h2O3qGmdmLt4rcU

[@mightyshenanigans2607]

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

[@doc9448]

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.

[@georios]

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

[@CS_n00b]

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

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

[@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

[@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.

[@krateskim4169]

Awesome explanation

[@samoboii]

this aint a medium question

[@abbbhhi]

yup, it's an easy level problem