Insertion finds where the new value belongs, then creates a node:
def insert(root, val):
if root == null:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
The search path determines the insertion point. New nodes always become leaves.
Time: . Space: for recursion.
Notice that insertion order determines tree shape. Inserting gives a balanced tree. Inserting gives a right-skewed stick.
That's why balanced BST variants (AVL, Red-Black) rebalance after insertions.