(5 points) Let T be a binary tree with n nodes. It is realized with an implement
ID: 3910550 • Letter: #
Question
(5 points) Let T be a binary tree with n nodes. It is realized with an implementation of the Binary Tree ADT that has O(1) running time for all methods except positions() and elements(), which have O(n) rnning time. Give the pseudocode for a O(n) time algorithm that uses the methods of the p given in Section 2.3.4. This traversal is known as the level order traversal. Assume the existence of an O(1) time visit(v) method (it should get called once on each vertex of T during the execution of your algorithm)Explanation / Answer
LevelOrder(tree){
for depth = 1 to height of the tree
forGivenLevel(tree,depth)
}
forGivenLevel(tree, depth){
if tree is NULL
return
if depth == 1
display tree->data
else if depth is greater than 1
forGivenLevel(tree->left,depth-1)
forGivenLevel(tree->right,depth-1)
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.