The binary tree can either be empty (no value, no children) or can have exactly two child trees and a value.

The binary tree is parameterized by a type argument. The type argument denotes the type of the value that each node stores.

The binary tree is defined as a sum type. Following are the alternatives for the sum type:

The empty tree is denoted by data constructor Leaf.

The binary tree node is a product type (BinaryTree) implemented using record syntax, with the following fields:

left: This denotes the left binary tree

val: This indicates the value of the node

right: This denotes the right binary tree

Since leftand right are of type BinaryTree, this is a recursively defined data type.

The helper function empty ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training,
learning paths, books, interactive tutorials, and more.