Binary Search Tree

• left.val < right.val
• all values are typically distinct
• search, insert, delete - $O(log n)$
• find closest - $O(log n)$
• sorted traversal - $O(n)$
• Applications: maintain sorted stream of data; implement doubly ended priority queue

Search

Recursive

• Time: $O(h)$, Space: $O(h)$

Python

def search(root, x):
    if root == None:
        return False
    elif root.val == x:
        return True
    elif root.val > x:
        return search(root.left, x)
    else:
        return search(root.right, x)

Iterative

• Time: $O(h)$, Space: $O(1)$

Python

def search(root, x):
    while root:
        if root.val == x:
            return True
        root = root.left if  root.val > x else root.right
    return False

Insert

Recursive

• Time: $O(h)$, Space: $O(h)$

Python

def insert(root, x):
    if root == None:
        return Node(x)
    elif root.val == x:
        return root
    elif root.val > x:
        root.left = insert(root.left, x)
    else:
        root.right = insert(root.right, x)
    return root

Iterative

• Time: $O(h)$, Space: $O(1)$

Python

def insert(root, x):
    if root == None:
        return Node(x)
    p = None # parent
    curr = root
    while curr:
        p = curr
        if curr.val == x:
            return root
        curr = curr.left if  curr.val > x else curr.right
    if p.val > x:
        p.left = Node(x)
    else:
        p.right = Node(x)
    return root

Delete

Recursive

• Time: $O(h)$, Space: $O(h)$

Python

def delete(root, x):
    if root == None:
        return
    if root.val > x:
        root.left = delete(root.left, x)
    elif root.val < x:
        root.right = delete(root.right, x)
    else:
        if root.left == None:
            return root.right
        elif root.right == None:
            return root.left
        else:
            succ = getSuccessor(root.right, x)
            root.val = succ
            root.right = delete(root.right, succ)
    return root

def getSuccessor(root, x):
    while root.left:
        root = root.left
    return root.val