labelling the leaves of binary tree

Question

I am trying to label the leaves of binary tree with numbers starting from zero and incrementing. Here's my definition of binary trees

  type btree = I of int | Node of string * btree * btree

My function when applied should label the tree leaves with numbers starting from the leftmost leaf, labeled with zero. for ex. Node("a", Node("b", I 25, I 54), Node("c", I 12, I 47)) should return the tree Node("a", Node("b", I 0, I 1), Node("c", I 2, I 3)). How can I do this? I tried to write code but it did not give suitable result. Here's my code:

 let mark bst =
  let number x = function
  |Node(a, I b, I c) -> Node(a, I x, I (x + 1))
  |Node(a, b, I c) -> Node(a, (number x b), I(x + 1))
  |Node(a, I b, c) -> Node(a, x, (number (x + 1) c)
  |Node(a, b, c) -> Node(a, (number x b), (number x c))
 in number 0 bst

This code is compiling fine but numbers the left and right subtrees separately from the beginning i.e. 0. Please help!!

torbonde torbonde · Accepted Answer · 2013-08-12T13:14:51

The following should work. It takes care of the subtrees one by one.

let mark bst = 
  let rec number = function
    | (x, I a) -> (x+1, I x)
    | (x, Node(a, b, c)) -> 
    let p1 = number (x,b) in
    let p2 = number ((fst p1),c) in
    ((fst p2),Node(a,(snd p1), (snd p2)))
  in snd (number (0,bst))

Here is what I got when running it on your example. Honestly, it's the only example I have tried, though.

# let tr =  Node("a", Node("b", I 25, I 54), Node("c", I 12, I 47));;
val tr : btree = Node ("a", Node ("b", I 25, I 54), Node ("c", I 12, I 47))
# markit tr;;
- : btree = Node ("a", Node ("b", I 0, I 1), Node ("c", I 2, I 3))

Explanation of the code: To label each leaf uniquely in ascending order, left to right, you have to look at each subtree, one at the time. After looking at the left subtree, you need to know how far you have come in the labelling-process, i.e. what the next label is. To do obtain this ability, my function number returns a pair of type int * btree, whereas yours return a btree. The int in the pair is the next unused label. Returning a pair, allows us to have two return-values. Clever!

I suppose you understand the first two lines, since they are identical to yours (almost - remember to use let rec when defining recursive functions). Within the function mark the number function is initiated in the last line - just like in your code as well. The difference is that, instead of giving the function two input-values, as you do, I give it one; a pair of values. In the end, though, all we want is the second entry in the pair, which we extract by using snd. In lines 3-4, we check if we are looking at an integer or a node (i.e. a leaf or a subtree). Note that accordig to your type definition, these two cases are the only possibilities. If we are looking at a node, we will need to traverse the left subtree firstly, which happens in line 5. After traversing the righ subtree, we still need to pass the next unused label down to the parent node, which is why we need line 6. In line 7, the return-pair is assembled.

Wow. That became quite lenghty. But I hope it clearified things somewhat. If not, please ask again!

labelling the leaves of binary tree

1 Answers