Insert into BST Solution

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: $O(h)$. Space: $O(1)$ iterative.