I need to solve this problem. I really have no clue. Any help would be greatly appreciated. I guess a traversal needs to be done but I have no idea how to attack this problem. Thanks in advance.
Consider again the following 1st datatype definition of a binary tree:
datatype 'a tree = Empty | Node of { lT: 'a tree, key: 'a, rT: 'a tree }
After you have written some functions for binary trees defined by this datatype, you would like to test them. You search online for test cases and find a database with binary trees that are actually defined using the following 2nd datatype:
datatype 'a tree = Empty | Node of 'a tree * 'a * 'a tree
Write a function "convert" that takes as input a binary tree of the second datatype and converts it into the equivalent tree of the first datatype.
You are correct, you need to traverse the tree, which can be elegantly achieved in SML by using pattern matching. You will want to case on the input tree, if it is Empty then simply return Empty. If it is a Node, then you will want to recursively convert the left and right subtrees and place those results into the other representation. This shouldn't require any more than 4 lines of code.