Question

A binary tree data type is defined in OCaml as follows:

type 'a binary_tree =
| Empty
| Node of 'a * 'a binary_tree * 'a binary_tree;;

The mirror of a binary tree is defined as the tree obtained by reversing its left and right subtrees at each level. Write an OCaml function

is_mirror: 'a binary_tree -> 'a binary_tree -> bool = <fun>

to determine if one tree is the mirror of another.

Your function must take into account the values in the nodes as well.

Answer 1

Here is the complete OCaml code for the given task. I have added comments for a better understanding of the same.

let rec is_mirror a b = match (a,b) with
| (Empty,Empty) -> true (* Both are Empty then mirror*)
| (Node(x1,y1,z1), Node(x2,y2,z2)) -> if(x1 = x2 && (is_mirror y1 z2) && (is_mirror y2 z1)) then true else false (* Left must be mirror of right and right must be mirror of left*)
| (_, _) -> false;; (*Otherwise False*)

You can comment below the answer in case of any doubts and I will be happy to help.

Please give a thumbs up if the answer could be of help!

All the best!