Question

5a

Please code in language Ocaml

In each of the three parts in this problem, you will get full credit if you use foldT and define at most one helper function.

(a) Define an OCaml function leafCount : ’a binTree -> int which returns an integer representing the total number of leaves in a tree.

Starter Code:

type 'a binTree =
| Leaf
| Node of 'a * ('a binTree) * ('a binTree)

let leafCount (t : 'a binTree) : int = (* your work here *) 0

Answer 1

ANSWER:

Given That data Define an OCAML function leaf Count : ’a bin tree -> int which returns an integer representing the total number of leaves in a tree.

SO

For leaf Count: If the current node is an internal node (non-leaf), then the sum of lea fCount on the left and right sub trees is returned. If it is a leaf, then 1 is returned, else 0.

While counting the number of leaves, if we come across an empty Node, then we return 0, else if the node is a leaf we return 1 or else we recursively call the leaf Count function on the left and right sub trees and sum the values.

Note: In the given tree definition, Leaf refers to an empty node (This terminology is quite confusing, but I have stuck to it for the sake of consistency).

Consider this tree as a small example.

   The expected answer for the number of leaves in this tree is 2.

Now examine the code snippet below. (Ocaml)

Ocaml Code pasted below:

type 'a bin Tree =
   | Leaf
   | Node of 'a * ('a bin Tree) * ('a bin Tree)

let rec leaf Count = function
   | Leaf -> 0
   | Node(_, Leaf, Leaf) -> 1
   | Node(_, l, r) -> leaf Count l + leaf Count r ;;

leaf Count my_tree