Tree Oz MOOC

Tree.oz

declare
fun {Infix Tree}
   case Tree
   of leaf then nil
   [] btree(K left:L right:R) then
      {Append {Append {Infix L} [K]} {Infix R}}
   end
end

declare
fun {FromListToTree L}
   local InsertTree TreeBuilder in
      fun {InsertTree K Tree}
	 case Tree
	 of btree(V) andthen K==V then Tree
	 [] btree(V left:L right:R) andthen K<V then btree(V left:{InsertTree K L} right:R)
	 [] btree(V left:L right:R) andthen K>V then btree(V left:L right:{InsertTree K R})
         else btree(K left:leaf right:leaf)
	 end
      end
      fun {TreeBuilder L Tree}
	 case L
	 of H|T then {TreeBuilder T {InsertTree H Tree}}
         else Tree
	 end
      end
      {TreeBuilder L leaf}
   end
end

declare
T = {FromListToTree [5 3 4 67 8 34 56]}

declare
fun {FromTreeToList Tree}
   local TreeToListBuilder in
      fun {TreeToListBuilder Trees}
	 case Trees
	 of nil then nil
	 [] T|Ts then
	    case T
	    of leaf then {TreeToListBuilder Ts}
	    [] btree(K left:L right:R) then {TreeToListBuilder L|K|R|Ts}
	    [] K then K | {TreeToListBuilder Ts}
            else nil
	    end
         else nil
	 end
      end
      {TreeToListBuilder [Tree]}
   end
end

{Browse {FromTreeToList T}}

declare
fun {NumLeaves Tree}
   case Tree
   of btree(V left:L right:R) then {NumLeaves L} + {NumLeaves R}
   else 1
   end
end

declare
fun {IsBalanced Tree}
   case Tree
   of btree(V left:L right:R) then
      local NumL NumR in
	 NumL = {NumLeaves L}
	 NumR = {NumLeaves R} 
	 (NumL == NumR  orelse {Number.abs (NumL - NumR)} == 1) andthen {IsBalanced L} andthen {IsBalanced R}
      end
   else true
   end
end