A complete binary tree with N nodes may be stored in an array A of length N by storing the root at A[0],and then storing in successive array locations the nodes of the tree in increasing order of the level of nodes.If nodes in the same level are stored in left to right order,then the parent of the node stored at A[k] will be stored at
A) A[(k-1)/2]
B) A[k-1]
C) A[2k+1]
D) A[k/2]

Question

Quizplus · Accepted Answer

In a complete binary tree, the left child of a node at index k is at index 2k+1 and the right child is at index 2k+2. The parent of a node at index k can be obtained by the formula (k-1)/2. Therefore, the parent of the node stored at A[k] will be stored at A[(k-1)/2]. Option A is the only choice that matches this formula.

A Complete Binary Tree with N Nodes May Be Stored