(*** Finitely-branching trees ***)

datatype 
  'a FBtree = node of 'a * 'a FBtree list ;

val mytree 
  = node(0,
         [node(2, 
               [node(3,[]),
                node(7,[]),
                node(5,[])]),
          node(9,[]),
          node(10,[])]) ;

val mytree1
  = node(0,
         [node(2, 
               [node(4,
                     [node(1,[])]),
                node(8,[]),
                node(6,[])]),
          node(8,
               [node(11,[]),
                node(13,[])]),
          node(10,[])]) ;

(*** Breadth-first search ***)

fun bfs P t
  = let fun auxbfs [] = NONE
          | auxbfs( node(n,F)::T )
              = if P n then SOME n
                else auxbfs( T @ F ) ;
    in 
      auxbfs [t]
    end ; 

bfs (fn x => x mod 2 = 1) mytree ;
bfs (fn x => false) mytree ;

bfs (fn x => x mod 2 = 1) mytree1 ;

(*** Depth-first search ***)

fun dfs P t
  = let fun auxdfs [] = NONE
          | auxdfs( node(n,F)::T )
              = if P n then SOME n
                else auxdfs( F @ T ) ;
    in 
      auxdfs [t]
    end ; 

dfs (fn x => x mod 2 = 1) mytree ;
dfs (fn x => false) mytree ;

(*** Version without append ***)

fun dfs' P t
  = let
      fun auxdfs( node(n,F) )
            = if P n then SOME n
              else foldl
                     (fn(t,r) => case r of NONE => auxdfs t | _ => r)
                     NONE
                     F ;
    in
      auxdfs t
    end ;

dfs' (fn x => x mod 2 = 1) mytree ;
dfs' (fn x => false) mytree ;

(*** Version without append; raising an exception when successful ***)

fun dfs0 P (t: 'a FBtree)
  = let 
      exception Ok of 'a;
      fun auxdfs( node(n,F) ) 
            = if P n then raise Ok n
              else foldl (fn(t,_) => auxdfs t) NONE F ;
    in 
      auxdfs t handle Ok n => SOME n 
    end ;

dfs0 (fn x => x mod 2 = 1) mytree ;
dfs0 (fn x => false) mytree ;

dfs (fn x => x mod 2 = 1) mytree1 ;
dfs0 (fn x => x mod 2 = 1) mytree1 ;