## Binary Trees

### External Interface

- tree CreateEmptyTree ()

// Create an empty binary tree

- tree CreateTree (labeltype label, tree T1, tree T2)

// Create tree with root label, left child T1, right child T2

- MakeLeftChild (tree child, tree T)

// Make child the left subtree of T

- MakeRightChild (tree child, tree T)

// Make child the right subtree of T

- tree LeftChild (tree T)

// Return the left subtree of T

- tree RightChild (tree T)

// Return the right subtree of T

- labeltype Label (tree T)

// Return the label at root of T

### Implementations

- Array of nodes, each of which holds the index of its left
and right child.

- Same as above, using dynamic allocation for nodes, and pointers
(rather than an index) to represent each node.