BST Lookup and Update

lookup

lookup navigates the tree by comparing the sought key against each node’s key:

exception Missing of string

let rec lookup b = function
  | Br ((a, x), t1, t2) ->
      if b < a then
        lookup b t1
      else if a < b then
        lookup b t2
      else
        x
  | Lf -> raise (Missing b)

Three cases at each branch:

• Smaller: search left subtree.
• Greater: search right subtree.
• Equal: return the stored value.
• Leaf reached: the key is not present; raise Missing.

In a balanced tree, lookup is O(log n). The exception is parameterised with the missing key so the caller knows what was sought.

update

update follows the same search path but reconstructs the tree along the way:

let rec update k v = function
  | Lf -> Br ((k, v), Lf, Lf)
  | Br ((a, x), t1, t2) ->
      if k < a then
        Br ((a, x), update k v t1, t2)
      else if a < k then
        Br ((a, x), t1, update k v t2)
      else (* a = k *)
        Br ((a, v), t1, t2)

Functional update: path copying

The key insight is that update does not modify the existing tree in place. Instead, it creates a new tree that shares unchanged subtrees with the original:

Case	Action
k < a	Update left subtree; share right subtree unchanged
k > a	Update right subtree; share left subtree unchanged
k = a	Replace value only; share both subtrees unchanged

Only the nodes on the path from the root to the updated node are copied. Unchanged subtrees are shared between the old and new trees. For a balanced tree, this means O(log n) time and O(log n) extra space per update. This is a classic example of persistent (or purely functional) data structures: old versions remain valid and accessible after updates.