We’re asked to implement the algorithm to add a node to a binary search tree. We just recursively call this function until we hit a non-existant node, then root.left or root.right will be the new node - if the value of the new node is less than root or greater, respectively.
The solution is as follows:
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root_ Time Complexity:
O(n) - We inspect all nodes in the binary search tree.
_ Space Complexity:
O(n) - Our call stack can grow as large as the number of nodes in the binary search tree.