Skip to content

Instantly share code, notes, and snippets.

@n2westman

n2westman/isSearch.ml

Created January 1, 2015 02:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save n2westman/f18b51541847f6362060 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save n2westman/f18b51541847f6362060 to your computer and use it in GitHub Desktop.
Download ZIP
Binary Tree Check OCaml
Raw
isSearch.ml
(* Tail Recusrive Check on if a Binary Tree is a search binary tree *)
type Node = Internal of Node * int * Node | Leaf of int
type Wrapper = W of Node * int * int
let isSearch tree =
let rec isSearchHelper ret wlist =
match wlist with
[] -> ret
| [W(n, minn, maxx)::rest] -> match n with
Leaf(v) -> isSearchHelper (ret && (minn<=v) && (v<maxx)) rest
| Internal(l,v,r) -> isSearchHelper (ret && (minn<=v) && (v<maxx)) (W(l,minn,v)::W(r,v,maxx)::rest)
in isSearchHelper true [W(tree,min_int,max_int)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment