Finding the insertion spot

To insert a value into a BST, search for it. If it is smaller than the current node, go left. If it is larger, go right. When you fall off the tree by reaching an empty spot, that empty position is exactly where the new node must go.

It is like finding where a new book belongs on a sorted shelf: you follow the same path a search would take, and put it where the path ends.

Empty spot: create the new node there.

Steer: smaller goes left, otherwise right.

Inserting 5 into [4, 2, 7, 1, 3]

Search for 5 as if it were there. 5 > 4: go right.

Move 1 of 3

Re-linking pointers

In the recursive version, each call hands back the root of its subtree, and the caller stores it back as its left or right child. Most of the time that changes nothing, but at the bottom it connects the freshly made node to the tree.

This is like passing a parcel along a chain of hands: the last hand finally holds the new item.

Return the root: always hand back the subtree's root so the link is kept.

Existing links: all other links in the tree stay unchanged.

In code

def put(node):
    if not node:
        return TreeNode(val)
    if val < node.val:
        node.left = put(node.left)
    else:
        node.right = put(node.right)
    return node

return put(root)