Several implementations of a general tree ADT are described

Several implementations of a general tree ADT are described.

Draw the representation of the tree that is being described.

Analyze the running time for each implementation for each of the following methods:

Parent, Root, Left_Most_Child, Right_Sibling, Print, Find

Note: Some implementations may not able to perform all of these operations. If that is the case, say so!

State any other limitations of the design.

1. Create a linear array, Arr, in which the nodes of the tree are the indices of the array. Each cell of the array contains the label of the parent of that node. The value stored for the parent of the root is NULL.

2. Create a linear array, Arr, in which the nodes of the tree are the indeces of the array. Each cell of the array contains a pointer to a linked list of the node's children.

3. Create a two-dimensional, nx2 array, Arr. The indices of the array are the nodes of the tree. The first column of the array stores the array index of the leftmost child of the node. The second column stores the array index of the right sibling of the node. If a node does not have a leftmost child or a right sibling, store NULL.

4. Each node, N, is represented by a structure consisting of 3 parts: a space for the label of N, a pointer to a linked list of N's siblings, and a pointer to a linked list of N's children.