CODEWITHSUNDEEP
binary-treesmlml
Ahmed Riza
Ahmed Riza

Reputation: 53

Creating an instance of a Binary Tree (Programming Standard ML by Robert Harper)

In the online book by Robert Harper (Programming Standard ML, on page 88, we have the following definition of a binary tree:

datatype 'a tree =
  Leaf
| Node of 'a branch * 'a branch
and 'a branch =
  Branch of 'a * 'a tree;

I wanted to create the following example tree (that conforms to the above definition of a tree)


           10
          /  \
         5   11
        / \
       2   6

I am strugglig to create the root node. What I've got so far is:

val two = Branch (2, Leaf);
val six = Branch (6, Leaf);
val eleven = Branch (11, Leaf);
val five = Branch (5, Node (two, six));
val ten = Branch (10, Node (five, eleven));

But then ten isn't the root of the tree. How'd I form the root of this tree?

Upvotes: 1

Views: 134

Answers (3)

Alex Veleshko
Alex Veleshko

Reputation: 1242

As mentioned in the book, this particular definition attaches data to branches and not nodes. Therefore you cannot represent your tree example with this tree definition. You need to redraw the tree and place numbers near branches instead of in nodes:

         *
     5  / \ 11
       /   \
      *     *
   2 / \ 6
    /   \    
   *     *

Then you can construct it in code as

val two = Branch (2, Leaf);
val six = Branch (6, Leaf);
val five = Branch (5, Node (two, six));
val eleven = Branch (11, Leaf);
val root = Node (five, eleven);

What is not mentioned in the book is that you can only represent a full binary tree with this definition, that is, a tree in which every node has either no or precisely two children.

An arbitrary binary tree with marked branches can be defined like this:

datatype 'a tree =
    Node of 'a branch * 'a branch
and 'a branch =
    NoBranch
  | Branch of 'a * 'a tree;

An empty tree then is Node (NoBranch, NoBranch) and you "cut" the right branch of the root in the example above like this:

val leaf = Node (NoBranch, NoBranch);
val two = Branch (2, leaf);
val six = Branch (6, leaf);
val five = Branch (5, Node (two, six));
val root = Node (five, NoBranch);

Upvotes: 2

molbdnilo
molbdnilo

Reputation: 66459

That's a different tree variation; "a notion of binary tree in which data items are associated with branches, rather than nodes" (my emphasis).
Your tree has data in the nodes in the more common way and conforms to the first variant, on page 85.
It's not surprising that you can't directly represent your structure as a different structure.

Upvotes: 5

Ahmed Riza
Ahmed Riza

Reputation: 53

If I reformulate the tree, i.e. create a new tree as follows

           root
           /  \
         10    12
        /  \
       5   11
      / \
     2   6

then it's trivial, of course

val two = Branch (2, Leaf);
val six = Branch (6, Leaf);
val eleven = Branch (11, Leaf);
val twelve = Branch(12, Leaf);
val five = Branch (5, Node (two, six));
val ten = Branch (10, Node (five, eleven));
val root = Node (ten, twelve);

As I can see from the type of the tree definition, each node must have two braches.

Upvotes: 0

Related Questions