NOTE: You have only TWO attempts. We will only look at the first two attempts an
ID: 3800486 • Letter: N
Question
NOTE: You have only TWO attempts. We will only look at the first two attempts and all others will be discarded. Please read the directions carefully. You are given a binary tree of the form Root 4 87 56 24 92 107 76 42 42 78 90 88 44 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)Explanation / Answer
The correct order which will be printing are:
d). 7, 8, 6, 7, 25, 42, 42, 22,....
As per the algorithm, it will start traversing from the root node 4, and recursivly check whether its left node is null or not, if it is not null, that means if a left node is present then this algorithm is again called recursively on that left node so it will go to node 3, then to its left node 7. The node 7 has no left node so then according to the algorithm, it will print the node value ie, 7 will be printed first and then it will print its linked list of next nodes, ie, node 7 has linked list of next node which has only one element in it, which is 8, so it will be printed next. After printing the linked list associated with the node 7, it will check whether node 7 has any right node, if it is present, then the whole algorithm is called recursively on that right node, here there is no right node for node 7, thus it will go one level up the iteration and reaches node 3 and it will print the node key 3, then go to its right node, ie node 22, then go recursively to its left node 25, which has no left and right childs so it will print node key 25 and its linked list elements 42, 42, then goes one level up to node 22, like so on..
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.