BST insert

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.

Exercise 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).

Show example 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)

Test yourself

Insert direction

if val < node.val:
    node.left = insert(node.____, val)

Show answer

if val < node.val:
    node.left = insert(node.left, val)

BST insert: match the terms

Smaller

Go left
Larger

Go right
Equal

Stop
Null

New node
How long does insert take (balanced)?
- O(1)
- O(n)
- O(log n)
- O(n^2)
Show answer

O(log n) — O(log n)

Next lesson: BST search

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies