(* Programmieraufgabe P-46 (baeume.ml)				*)
(* Leonhard Fellermayr								*)
(* Mat.Nr. 22128130XXXX								*)

(* Typdeklaration *)

type 'a bintree = Empty | Build of 'a * 'a bintree * 'a bintree;;

(* Ein paar BŠume zum Testen *)

let baum1 = Build (1,Build(2,Empty,Empty),Build(3,Empty,Empty));;
let baum2 = Build (1, Build (2, Build (5, Empty, Empty), Build (7, Build (40, Empty, Empty), Build (50, Empty, Empty))), Build (3, Empty, Build (9, Empty, Empty)));;
let baum3 = Build (2,Empty,Empty);;
let baum4 = Build (2,Build(5,Empty,Empty),Build(7, Empty,Empty));;
let baum5 = Build (7,Build(40,Empty,Empty),Build(50,Empty,Empty));;

(* aus der VL *)

let root  (Build (x,_,_)) = x;;
let left  (Build (_,l,_)) = l;;
let right (Build (_,_,r)) = r;;

(* subtree *)

let rec subtree tb b = match b with
    Empty           -> false
  | x when (x = tb) -> true
  | _               -> subtree tb (left b) || subtree tb (right b);; 

(* ispath *)

let rec ispath l t = match (l,t) with
     (x::xs,Empty) -> false
   | (x::xs,_)     -> if (root t) == x then
                        (ispath xs (left t)) || (ispath xs (right t))
                      else false
   | ([],_)        -> true;;

(* leaves *)

let rec leaves t = match t with
    Empty                 -> []
  | Build (x,Empty,Empty) -> [x]
  | _                     -> leaves (left t) @ leaves (right t)

(* EOF *)