Question

A heap can be encoded either as an array, or as a full binary tree. For this question, write a function that takes the array representation of a heap and outputs its binary tree representation. More specifically, you should write a function with the specifications given below.

Specifications for the function:

# def arrayToTree(A, j):

# input: array A representing a heap, an index j in [0:len(A)]

# output: a Node object storing the heap with root j in the array A

Should use a recursive algorithm.

All I want is an explanation! Can you please explain this question really simply so I can understand and maybe explain the algorithm but no code please! Can you explain what this problem is asking and how someone with barely any knowledge of python might do this. Please don't code anything, just give explanations

Answer 1

The problem is about converting the given heap in array to heap in full binary tree.

For Example, the heap is [1,2,3,4,5,6,7] in array data structure

And in full binary fill tree it looks as follows:

                            1

                          / \

                       2       3

                    /    \     /    \

                  4      5 6      7

The queston is about converting the heap array from index j into heap fulll binary tree.

For Example, the heap is [1,2,3,4,5,6,7] in array data structure

And let the index be 2, then the heap is [3,4,5,6,7] in array data structure

And in full binary fill tree it looks as follows:

                            3

                          / \

                       4       5

                    /    \

                 6       7

Our target is to achieve this and return the root node of this tree.

Python code for above problem

class Node:
   def __init__(self,data):
       self.data=data
       self.left=None
       self.right=None
  
   def set_left(self,left):
       self.left=left
      
   def set_right(self,right):
       self.right=right
  
def set_pointers(nodes,j,length):
   if(j==length):
       return
   left=2*j+1
   right=2*j+2
   if(left<length):
       nodes[j].set_left(nodes[left])
   if(right<length):
       nodes[j].set_right(nodes[right])
   set_pointers(nodes,j+1,length)
  
def arrayToTree(A,j):
   nodes=[]
   A=A[j:]
   for i in range(len(A)):
       nodes.append(Node(A[i]))
      
   set_pointers(nodes,0,len(A))
   return nodes[0]
  
def inorder(root):
   if root is None:
       return
   print(root.data),
   inorder(root.left)
   inorder(root.right)
  
def test_case_1():
   arr=[1,2,3,4,5,6,7]
   root=arrayToTree(arr,2)
   print("Array:"),
   print(arr[2:])
   print("Heap:"),
   inorder(root)
   print("")
  
def test_case_2():
   arr=[1,2,3,4,5,6,7]
   root=arrayToTree(arr,0)
   print("Array:"),
   print(arr[0:])
   print("Heap:"),
   inorder(root)
   print("")

def main():
   test_case_1()
   test_case_2()
  
main()

Sample output

Array: [3, 4, 5, 6, 7] Heap: 3 4 6 7 5 Array: [1, 2, 3, 4, 5, 6, 7] Heap: 1 2 4 5 3 6 7

Mention in comments if any mistakes or errors are found. Thank you.