1

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?

Improve this question
3
  • 1
    I'm no CS expert, but why would it not be the root? It has no parents but does have children, and the rest of the tree can be accessed using it as a starting point. You could always track the root with a variable and update it as necessary, which will be needed later in binary trees. Commented Mar 23, 2024 at 21:21
  • @l3l_aze Please see the definition of the tree datatype at the start of the question. Commented Mar 23, 2024 at 21:26
  • 3
    What an odd definition of a binary tree, where the root cannot have a value, vs. something like: datatype 'a tree = Leaf | Node of 'a * 'a tree * 'a tree Commented Mar 23, 2024 at 23:56

3 Answers 3

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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);
Improve this answer

2 Comments

There are other definitions of trees which are more traditional in the book, for example, the definition on page 85. I am not entirely sure of the motivation of the author in introducing the particular form on page 88, other than an academic exercise.
@AhmedRiza There is no motivation for the other examples either, beyond "we can define recursive data structures that are like this". You just happen to be familiar with them already.
0

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.

Improve this answer

1 Comment

Indeed, one might argue that the tree defined on page 88 doesn't make much sense, as it cannot represent a tree holding an odd number of values.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.