BST insert
- Algorithms course
- Intermediate
- Lesson 30/80
- 4 min
Insert a new value following the rule.
BST insert
When inserting into a BST we preserve the rule: if the value is smaller than the root recurse left, if larger recurse right. When we reach a null node we create a new node there.
If the value already exists we usually do nothing (no duplicates) or insert to the right. This choice depends on the application.
Insertion is O(log n) (if balanced); O(n) if unbalanced.
Duplicates
How to handle duplicate values in a BST is a design decision. Three common approaches exist.
First: reject duplicates (most common). Second: insert into the right subtree (smaller-or-equal on the right). Third: keep a counter in the node.
In this course we use the reject-duplicates approach: when an equal value comes, do nothing.
Practice BST insert
Write insert(node, val). Smaller left, larger right; None means new node. Print 5 3 7 with root = None; for v in [5,3,7]: root = insert(root, v); print(root.val, root.left.val, root.right.val).
Starter code
def insert(node, val):
# Insert into BSTSample solution
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(node, val):
# Insert into BST
if node is None:
return Node(val)
if val < node.val:
node.left = insert(node.left, val)
elif val > node.val:
node.right = insert(node.right, val)
return node
root = None
for v in [5, 3, 7]:
root = insert(root, v)
print(root.val, root.left.val, root.right.val)Expected output
5 3 7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Insert direction
if val < node.val:
node.left = insert(node.____, val)if val < node.val:
node.left = insert(node.left, val)Explanation: left is right.
2 BST insert: match the terms
| Term | Meaning |
|---|---|
Smaller |
Go left |
Larger |
Go right |
Equal |
Stop |
Null |
New node |
3 How long does insert take (balanced)?
- O(1)
- O(n)
- O(log n) Correct answer
- O(n^2)
Explanation: O(log n)