worldtree.sml

(* worldtree.sml O(nlogn) *)

local
  (* Int tree struct (key,left,right) *)
  datatype tree = Null
                | Node of int * tree *  tree

  (* function to read input *)
  fun parse file =
    let
      fun readInt input =
        Option.valOf (TextIO.scanStream (Int.scan StringCvt.DEC) input)
      val inStream = TextIO.openIn file
      val n = readInt inStream
      val _ = TextIO.inputLine inStream
      val root_key = readInt inStream
      fun readNode 0 = Null
        | readNode key = Node(key,(readNode (readInt inStream)),(readNode (readInt inStream)))  
    in
      readNode root_key
    end

  (* Inorder print function *)
  fun InorderPrint Null = ()
    | InorderPrint (Node (n,left,right)) = (
        InorderPrint(left);
        print((Int.toString n)^" ");
        InorderPrint(right)) 
   
  (* A function to find the 1st Inorder Node *)
  fun MostLeft (Node (n,Null,_)) = n 
    | MostLeft (Node (n,left,_)) = MostLeft left
    | MostLeft Null = 0 (* This shall never be used / Just for the warning *) 

  (* Main solving function *)  
  (* If its Null return Null*)
  fun solve Null = Null
  
    (* If Node is leaf return Node*)
    | solve (Node (n,Null,Null)) = (Node (n,Null,Null))
  
    (* If only the left child exists compare with parent *)
    | solve (Node (n,left,Null)) = (
        let
          val LEFT = solve(left)
        in
        if (MostLeft(LEFT) > n) then (Node (n,Null,LEFT)) (* Swap *)      
        else (Node (n,LEFT,Null))                         (* Don't swap *)        
        end )  
  
    (* If only the right child exists compare with parent *)
    | solve (Node (n,Null,right)) = (
        let
          val RIGHT = solve(right)
        in
        if (MostLeft(RIGHT) < n) then (Node (n,RIGHT,Null))  (* Swap *)    
        else (Node (n,Null,RIGHT))                           (* Don't swap *)     
        end )  
    (* If both children exist compare with each other *)
    | solve (Node (n,left,right)) = (
        let
          val LEFT = solve(left)
          val RIGHT = solve(right)
        in
        if (MostLeft(RIGHT) < MostLeft(LEFT)) then (Node (n,RIGHT,LEFT)) (* Swap *)
        else (Node (n,LEFT,RIGHT))                                       (*Don't*)         
        end )
in
fun arrange input =
      InorderPrint(solve(parse input))
end