CODEWITHSUNDEEP
treetime-complexitysml
sometimesdumb
sometimesdumb

Reputation: 1

How can I convert a tree to a list in SML in O(n) time complexity?

The list needs to be an in-order traversal. Here's what I have so far:

datatype tree =
   Empty 
 | Node of (tree * int * tree)

fun combine (t1 : tree, t2 : tree) : tree =
    case t1 of
      Empty => t2
    | Node(l1,x1,r1) => Node(combine(l1,r1),x1,t2)

fun TTL (t : tree) : int list =
   let val tree = combine(t, Empty) in
      case tree of
         Empty => []
       | Node(l, x, r) => x :: TTL(l)
   end

This doesn't output the list in the correct order, and I'm pretty stuck now. Please help.

Upvotes: 0

Views: 280

Answers (2)

Chris
Chris

Reputation: 36496

The answer posted by @molbdnilo works, but a further suggestion that doesn't format nicely as a comment. Take advantage of SML's pattern-matching facilities, type inference, and generic types.

You have a combine function:

fun combine (t1 : tree, t2 : tree) : tree =
    case t1 of
      Empty => t2
    | Node(l1,x1,r1) => Node(combine(l1,r1),x1,t2)

Let's strip out the unnecessary type annotations first:

fun combine (t1, t2) =
    case t1 of
      Empty => t2
    | Node(l1, x1, r1) => Node(combine(l1, r1), x1, t2)

Now, the case ... of isn't really necessary either because we can directly pattern match in the function's argument list in this case.

fun combine (Empty, t2) = t2
  | combine (Node(l1, x1, r1), t2) = Node(combine(l1, r1), x1, t2)

Lastly, there's no reason your tree type need only work on int.

datatype 'a tree = Empty | Node of ('a tree * 'a * 'a tree)

Hopefully as you get deeper into learning, some of these tips help make your code easier to reason about and more flexible.

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66371

Traverse the right subtree, then attach the node's value to that list, then traverse the left subtree while adding elements to this second list.
You can do this with a helper function that takes an accumulation parameter,

fun TTL t =
    let fun TTL' Empty ns = ns
          | TTL' (Node(l, x, r)) ns = TTL' l (x::TTL' r ns)
    in
        TTL' t []
    end

Upvotes: 1

Related Questions