CODEWITHSUNDEEP
binary-treesmlmltree-traversal
WilsonHoHK
WilsonHoHK

Reputation: 33

Standard ML Binary Tree Traversal

I am new to SML and doing a practice about tree traversal. This is the setting of question.

datatype 'a bTree = nil | bt of 'a bTree * 'a * 'a bTree;

I need to write a function inorder which accepts a binary tree and return a lists of all members of the tree in inorder traversal.

I wrote this line:

fun inorder(nil) = nil
  | inorder(bt(left,key,right)) = inorder(left) @ [key] @ inorder(right);

But get some error and don't know how to fix:

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Z list * 'Y bTree
in expression:
  (key :: nil) @ inorder right

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Y bTree * _
in expression:
  inorder left @ (key :: nil) @ inorder right

Upvotes: 2

Views: 2252

Answers (1)

molbdnilo
molbdnilo

Reputation: 66459

You've inadvertently hidden the nil list constructor and replaced it with your tree constructor of the same name.

This means that your first case,

inorder(nil) = nil

says that the result of inorder is a tree; its type is

'a bTree -> 'a bTree

and you can't append (@) a list to a 'a bTree.

Your code will work if you rename the empty tree constructor:

datatype 'a bTree = nilTree | bt of 'a bTree * 'a * 'a bTree;

fun inorder nilTree = nil
  | inorder (bt(left,key,right)) = inorder left @ [key] @ inorder right;

or use [] instead of nil.
Not hiding nil is the better solution, though.

Upvotes: 5

Related Questions