test.ml

open Base
open With_return

type node = { value: int; left: node option; right: node option }

let is_bst tree=
  with_return (fun r ->
      let rec tick = function
        | { value; left = None; right = None} -> (value, value)
        | { value; left = Some l; right = None} ->
          let (a, b) = tick l in
          if b <= value
          then (a, value)
          else r.return false
        | { value; left = None; right = Some ri} ->
          let (a, b) = tick ri in
          if a > value
          then (value, b)
          else r.return false
        | { value; left = Some l; right = Some ri;} ->
          let (la, lb) = tick l in
          let (ra, rb) = tick ri in
          if lb <= value && ra > value
          then (la, lb)
          else r.return false in
      tick tree |> ignore;
      true)

let tree = { value = 5;
             left = Some { value = 3;
                           left = Some { value = 1;
                                         left = None;
                                         right = None};
                           right = Some { value = 4;
                                          left = None;
                                          right = None}};
             right = Some { value = 7;
                            left = Some { value = 2;
                                          left = None;
                                          right = None };
                            right = Some { value = 9;
                                           left = None;
                                           right = None }}}