BinaryRandomAccessList-insert.ml

let size tree = match tree with
  | Leaf _ -> 1
  | Node ({size}) -> size
;;

let link tree1 tree2 = Node {
  size = (size tree1) + (size tree2);
  left = tree1;
  right = tree2;
};;

let rec pushTree tree digits = match digits with
  | [] -> [One tree]
  | Zero :: restDigits -> (One tree) :: restDigits
  | (One currentTree) :: restDigits ->
    Zero :: (pushTree (link tree currentTree) restDigits)
;;

let push element digits = pushTree (Leaf element) digits;;