New nodes always become leaves. Find the correct position and insert:
def insertIntoBST(root, val):
if root == null:
return TreeNode(val)
if val < root.val:
root.left = insertIntoBST(root.left, val)
else:
root.right = insertIntoBST(root.right, val)
return root
Iterative version:
def insertIntoBST(root, val):
if not root:
return TreeNode(val)
parent, current = null, root
while current:
parent = current
current = current.left if val < current.val else current.right
if val < parent.val:
parent.left = TreeNode(val)
else:
parent.right = TreeNode(val)
return root
Time: . Space: iterative.