Ex: Binary Trees

Let's start by creating a basic data type to represent a binary tree.
Recall that a binary tree has two main components: nodes and leaves, where each node leads to either 0, 1, or 2 other nodes, and nodes that lead to no other nodes (i.e. has no children) are called leaves.

Binary Tree
Enter the following three lines into the Coconut interpreter: 

data Empty()
data Leaf(n)              	
data Node(l, r)
This allows us to declare data types such that:
  • Empty() represents an empty binary tree
  • Leaf(n) represents a leaf with the value n
  • Node(l,r) represents a node with children l and r
Now suppose that we want to add a method such as finding the "size" of a certain data type. We can declare an empty tree's size as follows:

def size(Empty()) = 0
Alternatively, methods can be applied to existing data types as follows:

@addpattern(size)
def size(Leaf(n)) = 1

@addpattern(size)
def size(Node(l, r)) = size(l) + size(r)
Finally, let's put all of these elements into action with the following binary tree. Copy and paste the following code to make a binary tree with an empty left child node, a leaf with value 10 on the right, and finally to find its size. 

size(Node(Empty(), Leaf(10))) |> print
You should find that because the node has only one leaf, the size of this entire tree becomes 1.


Next
Previous