The usual recursive formulation of the function that computes the sum of a tree
let rec sum_tree t =
match t with
| Leaf -> 0
| Node (l, x, r) -> sum_tree l + x + sum_tree r
is not tail-recursive.
For a tail recursive implementation, you may need to use an auxiliary function of type
aux: int -> int tree list -> int
Hint: aux acc ts takes as input an accumulator acc as usual and a list of sub-trees obtained from the input tree. The idea is that when the list is empty, acc is the sum of all input-tree elements. Implement a tail recursive function sumtailrec that uses this idea.
sumtailrec: int tree -> int
Your solution must be strictly tail-recursive. The following solution sums all nodes on the left branch l and then all nodes on the right branch r is incorrect. Calling the aux function twice in the recursive code makes the function not tail-recursive because you need a stack frame for the first call. You should only call the aux function once in the recursive code. Following the hint above can correct this solution.
let rec aux (acc:int) (ts: int tree) =
match ts with | Leaf -> acc
| Node(l, x, r) -> (aux (aux (acc+x) l)) r
In [ ]:
let sumtailrec t =
(* YOUR CODE HERE *)
In [ ]:
let tree = construct [2;1;3] in
assert (sumtailrec tree = sum_tree tree)

If construct builds a binary search tree from a list of integers, the assertion should pass.

Here's a possible implementation of the sumtailrec function in a tail-recursive way using the aux function suggested:

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let sumtailrec t =

 let rec aux acc ts_stack =

   match ts_stack with

   | [] -> acc

   | Leaf :: ts' -> aux acc ts'

   | Node (l, x, r) :: ts' -> aux (acc + x) (l :: r :: ts')

 in

 aux 0 [t]

The aux function takes an accumulator acc and a stack of trees ts_stack. The stack initially contains only the input tree t.

In each iteration, it pops a tree ts from the top of the stack, and if ts is a leaf, it continues with the next tree on the stack.

If ts is a node, it adds its value to the accumulator acc and pushes its left and right subtrees onto the stack. The function returns acc when the stack is empty.

The sumtailrec function simply calls aux with an initial accumulator of 0 and a stack containing the input tree t. Finally, it returns the result of aux.

The function construct used in the test case is not defined, so I cannot test the function, but if construct builds a binary search tree from a list of integers, the assertion should pass.

Learn more about implement a tail-recursive function.

brainly.com/question/30020618

#SPJ11