Tree Traversal Target: 10s
Search for the insertion point, create new node there. Always inserts as a leaf. O(h) time.
def insertIntoBST(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insertIntoBST(root.left, val)
else:
root.right = insertIntoBST(root.right, val)
return root
# Iterative:
def insertIntoBST_iter(root, val):
node = TreeNode(val)
if not root: return node
cur = root
while True:
if val < cur.val:
if not cur.left: cur.left = node; break
cur = cur.left
else:
if not cur.right: cur.right = node; break
cur = cur.right
return rootType it from memory. Go.