A binary tree consists of a root containing a value that is an integer, a (possibly empty) left subtree, and a (possibly empty) right subtree. Such a binary tree can be represented by a triple (Left subtree, Root, Right subtree). Let the symbol nil denote an empty tree.

Example of binary tree inculde:

(nil, 13, nil) represents a tree with one node labled with the value 13.

((nil,3,nil),8,nil) represents a tree with 8 at the root, an empty right subtree, and a nonempty left subtree with root labeled by 3 and empty subtrees.

The following BNF specification describes this representation of binary tree.

::= nil | ( , , )

:: = |

:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Augement this grammar with attributes to carry out the following tasks:

a. A binary tree is balanced if the heights of the subtrees at each interior node are within one of each other. Accept only balanced binary trees.

b. A binary search tree is a binary tree with the property that all the values in the left subtree of any node N are less than the value at N, and all the values in

the right subtree of N are greater than or equal to the value of at node N. Accept only binary search trees.