You are given a binary tree of the form: Each node in the tree has a left child
ID: 3854821 • Letter: Y
Question
You are given a binary tree of the form:
Each node in the tree has a left child and a right child. Each of the children will be extended as a linked list. Every node has the following attributes: key, left node, right node, and next node. The next node allows a node, that is a part of the tree, to be extended as a linked list. The diamonds represent the next nodes, which are part of the linked list and are not considered as a part of the tree, i. e, they are not considered as a child node or a parent node, they are simply acting as an extension to a node of the binary tree (represented by squares).
The nodes are created using the following struct:
struct node{
int key;
node* parent; // parent node of the node in question
node* left; // left node of the node in question
node* right; // right node of the node in question
node* next; // next node to form the linked list
};
The following is the algorithm to traverse the tree:
void TraverseTree(node* currentNode)
{
if(currentNode->left != NULL)
{
TraverseTree(currentNode->left);
}
printKey(currentNode->key);
if(currentNode->next != NULL)
{
TraverseLinkedList(currentNode->next);
}
if(currentNode->right != NULL)
{
TraverseTree(currentNode->right);
}
}
functions used in the algorithm:
printKey - takes the key of the current node as the argument and prints it.
TraverseLinedList - used to traverse the Linked List and calls the printKey function as it iterates through the linked list.
Your job is to select the correct order in which the nodes are printed when the algorithm executes on the above Binary Tree starting at the root node.
Select one:
a. 8, 7, 7, 6, 3, 42, 42, 25, 9, 22, 44, 77, 88, 90, 11, 78, 4, 107, 76, 1, 56, 24, 87, 92, 0, 5
b. 7, 8, 3, 6, 7, 25, 42, 42, 22, 9, 78, 11, 90, 88, 77, 44, 4, 76, 107, 87, 24, 56, 1, 5, 0, 92
c. 3, 6, 7, 7, 8, 22, 9, 25, 42, 42, 78, 11, 90, 88, 77, 44, 4, 87, 24, 56, 1, 76, 107, 5, 0, 92
d. 25, 42, 42, 22, 9, 78, 11, 90, 88, 77, 44, 7, 8, 3, 6, 7, 4, 76, 107, 87, 24, 56, 1, 5, 0, 92
e. 4, 3, 6, 7, 7, 8, 22, 9, 25, 42, 42, 78, 11, 90, 88, 77, 44, 87, 24, 56, 1, 76, 107, 5, 0, 92
f. 3, 6, 7, 7, 8, 25, 42, 42, 22, 9, 78, 11, 90, 88, 77, 44, 4, 87, 24, 56, 1, 76, 107, 5, 0, 92
g. 7, 8, 25, 42, 42, 78, 11, 90, 88, 77, 44, 22, 9, 3, 6, 7, 76, 107, 5, 0, 92, 87, 24, 56, 1, 4
h. 25, 42, 42, 78, 11, 90, 88, 77, 44, 7, 8, 22, 9, 76, 107, 5, 0, 92, 3, 6 ,7, 87, 24, 56, 1, 4
i. 4, 3, 6, 7, 87, 24, 56, 1, 7, 8, 22, 9, 76, 107, 5, 0, 92, 25, 42, 42, 78, 11, 90, 88, 77, 44
Root 4 4 87 24 56 5 0 92 76 107 42 42 78 90 25Explanation / Answer
Answer is:
b. 7,8,3,6,7,25,42,42,22,9,78,11,90,88,77,44,4,76,107,87,24,56,1,5,0,92
1. As per the code, first input the function is parent node = 4 then as it have left child it call function recursively with left child and then its left child and when left child value is null it calls print function.
2. After that it check for next value in linked list and prints that and continue to check for next linked values and print if applicable.
3. When left nodes are printed it returns to root call and prints the value of root.
4. It then goes to right child tree.
5. Repeat above steps for right tree.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.