CODEWITHSUNDEEP
functional-programmingsml
anon_swe
anon_swe

Reputation: 9345

Standard ML: Modify depth function for binary tree

I'm given a depth function for a binary tree as follows:

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

Suppose I want to modify this depth function such that a single node will have depth 0 (as it is, a single node will have depth 1). How would I go about doing this?

I was thinking:

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

Does this look right?

Thanks,

bclayman

Upvotes: 1

Views: 102

Answers (1)

Matt
Matt

Reputation: 4049

This is close, but not quite right. depth(Node(Node(Empty,1,Empty),2,Empty) will recurse on the left subtree, which is a single node, so it will return 0. Then it will recurse on the right, which is empty, returning 0. You will then take the max of 0 and 0, returning 1, which is probably not what you want. Instead, you would have to match the empty case, and the singleton case as you have done, and for the default case, you will want to call the original version, that returns 1 for a single node.

Upvotes: 1

Related Questions