BST insert follows the same comparison logic as search but instead of returning when it finds the value, it follows the path until it hits a null child and inserts a new leaf node there. The BST property — left subtree smaller, right subtree larger — is automatically maintained. In a balanced tree this is O(log n).
Example: Insert 6 into the BST.
When to use this
→Building a BST from an array of values
→Maintaining a sorted dynamic set with fast insert/delete/search
→Implementing a sorted map / ordered dictionary
→Priority queues (heaps are better, but BSTs support order statistics)
BST insert follows the same path as search: compare the value at each node and go left if smaller, right if larger, until a null slot is found. Insert the new node there.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defbst_insert(node,val):
2
ifnodeisNone:returnNode(val)
3
ifval<node.val:
4
node.left=bst_insert(node.left,val)
5
else:
6
node.right=bst_insert(node.right,val)
7
returnnode
Quick check
Where is a new value always inserted in a BST?
What happens to BST performance if you insert values in sorted order?