Binary Search Tree

Overview

Full BST implementation using algebraic data types — insert, delete (with in-order successor replacement), membership check, min/max, in-order traversal, size, and depth. The 'a type parameter means this tree works with integers, strings, or any comparable type.

Type Definition

Model a tree in 3 lines — this is where OCaml shines:

type 'a tree =
  | Leaf
  | Node of 'a tree * 'a * 'a tree

Key Operations

Insert

let rec insert x = function
  | Leaf -> Node (Leaf, x, Leaf)
  | Node (left, v, right) ->
    if x < v then Node (insert x left, v, right)
    else if x > v then Node (left, v, insert x right)
    else Node (left, v, right)  (* duplicate: no change *)

In-Order Traversal (O(n) with Accumulator)

The accumulator pattern avoids O(n) list concatenation at each node, giving O(n) overall instead of O(n²):

let inorder tree =
  let rec aux acc = function
    | Leaf -> acc
    | Node (left, v, right) ->
      aux (v :: aux acc right) left
  in aux [] tree

Delete (with In-Order Successor)

Deleting a node with two children: replace it with the smallest value in the right subtree (the in-order successor), then delete that successor from the right subtree:

let rec delete x = function
  | Leaf -> Leaf
  | Node (left, v, right) ->
    if x < v then Node (delete x left, v, right)
    else if x > v then Node (left, v, delete x right)
    else match left, right with
      | Leaf, _ -> right
      | _, Leaf -> left
      | _ ->
        (match min_elem right with
         | None -> Leaf
         | Some s -> Node (left, s, delete s right))

Output

In-order: 1 3 4 5 6 7 8
Contains 4: true
Contains 9: false
Depth: 3
Size: 7
Minimum: 1
Maximum: 8
After deleting 3: 1 4 5 6 7 8
Contains 3 after delete: false