Standard ML: Size of binary tree computed incorrectly?

Question

My book has the following function which calculates the number of non-leaf nodes in a binary tree:

fun size Empty = 0 
    | size(Node(t_1, _, t_2)) = size t_1 + size t_2 + 1;

Suppose I want to calculate all nodes in a binary tree. How would I modify this function to do so?

Here's what I was thinking:

fun size Empty = 0
    | size(Node(Empty, _, Empty)) = 1
    | size(Node(t_1, _, t_2)) = size t_1 + size t_2 + 1;

Does this look right?

Thanks,

bclayman

Answer 1

Both of the implementations that you provided are actually the same. The second case of your second implementation is a special case of you your third pattern. For your first implementation, size(Node(Empty,1,Empty)) will recurse one the left subtree, returning 0, recurse on the right subtree, which returns 0, and then adds 1, yielding the result 1. In fact, if you switch the order of the second and third case, the compiler will tell you that it is redundant:

test.sml:3.5-5.38 Error: match redundant
      Empty => ...
      Node (t_1,_,t_2) => ...
-->   Node (Empty,_,Empty) => ...