Let T be a binary tree with n positions that is realized with an array representation A, and let f () be the level numbering function of the positions of T, as given in Section 8.3.2. Give pseudocode descriptions of each of the methods root, parent, left, right, isExternal, and isRoot.

Section 8.3.2:

83. Implementing Trees 8.3.2 Array-Based Representation of a Binary Tree An altemative representation of a binary tree Tis based on a way of numbering the positions of T. For every position pof T, let f(p) be the integer defined as follows. If pis the root of r, then f(p -0. pis the left child of position q,then fop)- 2 (g)+ 1 If p is the right child of position q, then f(p) -2f (g) +2 The numbering function f is known as a level numbering of the positions in a binary tree T, for it numbers the positions on each level of Tin increasing order from left to right. (See Figure 8.10.) Note well that the level numbering is based on potential positions within a tree, not the actual shape of a specific tree, so they are not necessarily consecutive. For example, in Figure 8.10(b), there are no nodes with level numbering 13 or 14, because the node with level numbering 6 has no children. (a) 10 11 12 13 14 (b) 2 L3 20 9 5 Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example. 83. Implementing Trees 8.3.2 Array-Based Representation of a Binary Tree An altemative representation of a binary tree Tis based on a way of numbering the positions of T. For every position pof T, let f(p) be the integer defined as follows. If pis the root of r, then f(p -0. pis the left child of position q,then fop)- 2 (g)+ 1 If p is the right child of position q, then f(p) -2f (g) +2 The numbering function f is known as a level numbering of the positions in a binary tree T, for it numbers the positions on each level of Tin increasing order from left to right. (See Figure 8.10.) Note well that the level numbering is based on potential positions within a tree, not the actual shape of a specific tree, so they are not necessarily consecutive. For example, in Figure 8.10(b), there are no nodes with level numbering 13 or 14, because the node with level numbering 6 has no children. (a) 10 11 12 13 14 (b) 2 L3 20 9 5 Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example