1.1 Preliminaries A binary tree is a tree data structure in which each node has at most two children, called the left child and the right child. Binary trees are a very popular data-structure in computer science. We shall see in this exercise how we can encode it using C arrays. The formal recursive definition of a binary tree is as follows. A binary tree is either empty, . or a node with two children, each of which is a binary tree. The following terminology is convenient: . A node with no children is called a leaf and a node with children is called an internal node. . If a node B is a child of a node A then we say that A is the parent of B. . In a non-empty binary tree, there is one and only one node with no parent; this node is called the root node of the tree. A binary tree T can be encoded in an array A with n+1 elements. Indeed, one can always label the nodes with the integers 1, 2,. n such that: . the root has label 1