Insert into a BST
Follow the search path until you hit null, then attach the new node as a child. About 8 minutes.
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.
Search for 5 as if it were there. 5 > 4: go right.
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.
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)Inserting 5 into a BST with root 10 and left child 3 attaches 5 as what?
- AThe right child of 3
- BThe left child of 3
- CThe right child of 10
Show the answer
The right child of 3. 5 < 10 (go left to 3), then 5 > 3 (go right of 3). Since 3 has no right child, 5 attaches there.
Insert into a BST
Given the root of a binary search tree (BST) and a value val to insert, insert val into the BST so that it remains a valid BST. Return the root of the modified BST. It is guaranteed that val does not already exist in the tree.
root = [4, 2, 7, 1, 3], val = 5 → [4, 2, 7, 1, 3, 5]
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, val ≤ 1,000,000 · val does not exist in the original tree