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.

Must be in pseudocode. Java.

8.3. Implementing Trees 331 8.3.2 Array-Based Representation of a Binary Tree An alternative representation of a binary tree Tis based on a way of numbering the positions of T. For every position p of T, let f(p) be the integer defined as follows. If p is the root of T, then f 0. If p is the right child of position q, then f(p) 2f(q)+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 T in 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.100b, 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) 10 12 11 16 19 25 15 3 1 7 4 Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example. 8.3. Implementing Trees 331 8.3.2 Array-Based Representation of a Binary Tree An alternative representation of a binary tree Tis based on a way of numbering the positions of T. For every position p of T, let f(p) be the integer defined as follows. If p is the root of T, then f 0. If p is the right child of position q, then f(p) 2f(q)+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 T in 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.100b, 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) 10 12 11 16 19 25 15 3 1 7 4 Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example