Java programming HelpNeed help with question: P 8.61P 8.61: Implement the binary tree ADT using the array-based representation described in Section 8.3.2. 8.3.2 Array-Based Representation of a Binary TreeAn alternative representation of a binary tree T is based on a way of numbering thepositions 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(p) = 0.• If p is the left child of position q, then ƒ(p) = 2ƒ(q)+1.• If p is the right child of position q, then ƒ(p) = 2ƒ(q) +2.The numbering function f is known as a level numbering of the positions in abinary tree T, for it numbers the positions on each level of T in increasing orderfrom left to right. (See Figure 8.10.) Note well that the level numbering is basedon potential positions within a tree, not the actual shape of a specific tree, so theyare not necessarily consecutive. For example, in Figure 8.10(b), there are no nodeswith level numbering 13 or 14, because the node with level numbering 6 has nochildren.(a)(b)1537+1613*83419910 11920510512 133*25761214264+66Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example. The level numbering function f suggests a representation of a binary tree T bymeans of an array-based structure A, with the element at position p of T stored atindex f(p) of the array. We show an example of an array-based representation of abinary tree in Figure 8.11.7338/ * ++40 1 2341*4411.952+125622 3 1955 6 7 8 9 10 11 12 13 14Figure 8.11: Representation of a binary tree by means of an array.One advantage of an array-based representation of a binary tree is that a posi-tion p can be represented by the single integer f(p), and that position-based meth-ods such as root, parent, left, and right can be implemented using simple arithmeticoperations on the number f(p). Based on our formula for the level numbering, theleft child of p has index 2ƒ(p) +1, the right child of p has index 2ƒ(p) +2, andthe parent of p has index [(ƒ(p) — 1)/2]. We leave the details of a complete array-based implementation as Exercise R-8.16.The space usage of an array-based representation depends greatly on the shapeof the tree. Let n be the number of nodes of T, and let f be the maximum valueof f(p) over all the nodes of T. The array A requires length N = 1 + fm, sinceelements range from A[0] to A[fM]. Note that A may have a number of empty cellsthat do not refer to existing positions of T. In fact, in the worst case, N = 2¹ - 1,the justification of which is left as an exercise (R-8.14). In Section 9.3, we willsee a class of binary trees, called "heaps" for which N = n. Thus, in spite of theworst-case space usage, there are applications for which the array representationof a binary tree is space efficient. Still, for general binary trees, the exponentialworst-case space requirement of this representation is prohibitive.Another drawback of an array representation is that many update operations fortrees cannot be efficiently supported. For example, removing a node and promotingits child takes O(n) time because it is not just the child that moves locations withinthe array, but all descendants of that child.

Question

Java programming HelpNeed help with question: P 8.61P 8.61: Implement the binary tree ADT using the array-based representation described in Section 8.3.2. 8.3.2 Array-Based Representation of a Binary TreeAn alternative representation of a binary tree T is based on a way of numbering thepositions 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(p) = 0.• If p is the left child of position q, then ƒ(p) = 2ƒ(q)+1.• If p is the right child of position q, then ƒ(p) = 2ƒ(q) +2.The numbering function f is known as a level numbering of the positions in abinary tree T, for it numbers the positions on each level of T in increasing orderfrom left to right. (See Figure 8.10.) Note well that the level numbering is basedon potential positions within a tree, not the actual shape of a specific tree, so theyare not necessarily consecutive. For example, in Figure 8.10(b), there are no nodeswith level numbering 13 or 14, because the node with level numbering 6 has nochildren.(a)(b)1537+1613*83419910 11920510512 133*25761214264+66Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example. The level numbering function f suggests a representation of a binary tree T bymeans of an array-based structure A, with the element at position p of T stored atindex f(p) of the array. We show an example of an array-based representation of abinary tree in Figure 8.11.7338/ * ++40 1 2341*4411.952+125622 3 1955 6 7 8 9 10 11 12 13 14Figure 8.11: Representation of a binary tree by means of an array.One advantage of an array-based representation of a binary tree is that a posi-tion p can be represented by the single integer f(p), and that position-based meth-ods such as root, parent, left, and right can be implemented using simple arithmeticoperations on the number f(p). Based on our formula for the level numbering, theleft child of p has index 2ƒ(p) +1, the right child of p has index 2ƒ(p) +2, andthe parent of p has index [(ƒ(p) — 1)/2]. We leave the details of a complete array-based implementation as Exercise R-8.16.The space usage of an array-based representation depends greatly on the shapeof the tree. Let n be the number of nodes of T, and let f be the maximum valueof f(p) over all the nodes of T. The array A requires length N = 1 + fm, sinceelements range from A[0] to A[fM]. Note that A may have a number of empty cellsthat do not refer to existing positions of T. In fact, in the worst case, N = 2¹ - 1,the justification of which is left as an exercise (R-8.14). In Section 9.3, we willsee a class of binary trees, called &#34;heaps&#34; for which N = n. Thus, in spite of theworst-case space usage, there are applications for which the array representationof a binary tree is space efficient. Still, for general binary trees, the exponentialworst-case space requirement of this representation is prohibitive.Another drawback of an array representation is that many update operations fortrees cannot be efficiently supported. For example, removing a node and promotingits child takes O(n) time because it is not just the child that moves locations withinthe array, but all descendants of that child.

Accepted Answer

In this question we will write java code for the binary Tree ADT using array based representation.

Java programming Help Need help with question: P 8.61 P 8.61: Implement the binary tree ADT using the array-based representation described in Section 8.3.2.