(rule the empty tree emptytreeor (rule it consists of node and two binary treesthe left subtree and right subtree againrule is the "base caseand rule is the "induction stepthis definition may appear circularbut actually it is notbecause the subtrees are always simpler than the original oneand we eventually end up with an empty tree you can imagine that the (infinitecollection of (finitetrees is created in sequence of days day is when you "get off the groundby applying rule to get the empty tree on later daysyou are allowed to use any trees that you have created on earlier days to construct new trees using rule thusfor exampleon day you can create exactly trees that have root with valuebut no children ( both the left and right subtrees are the empty treecreated at day on day you can use new node with valuewith the empty tree and/or the one-node treeto create more trees thusbinary trees are the objects created by the above two rules in finite number of steps the height of treedefined aboveis the number of days it takes to create it using the above two ruleswhere we assume that only one rule is used per dayas we have just discussed (exercisework out the sequence of steps needed to create the tree in figure and hence prove that it is in fact binary tree primitive operations on binary trees the primitive operators for binary trees are fairly obvious we have two constructors which are used to build treesemptytreewhich returns an empty treemaketree(vlr)which builds binary tree from root node with label and two constituent binary trees and ra condition to test whether tree is emptyisempty( )which returns true if tree is the emptytreeand three selectors to break non-empty tree into its constituent partsroot( )which returns the value of the root node of binary tree tleft( )which returns the left sub-tree of binary tree tright( )which returns the right sub-tree of binary tree these operators can be used to create all the algorithms we might need for manipulating binary trees for convenience thoughit is often good idea to define derived operators that allow us to write simplermore readable algorithms for examplewe can define derived constructorleaf(vmaketree(vemptytreeemptytreethat creates tree consisting of single node with label vwhich is the root and the unique leaf of the tree at the same time then the tree in figure can be constructed as