(5 points) Let T be a binary tree with n nodes. It is realized with an implement

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

This may help you in solvint the problem

import java.util.queue:

static class Node {

int data:

Node left;

Node right;

this.data=data;

left=null;

rigt=null;

}

if (root==Null)

return;

q.add(root);

q.add(null);

while (!q.isEmpty()){

System.out.println();

}

else {

q.add(curr.left);

if(curr.righht=!null)

q.add(curr.right);

}

public static void main(String[]args)

{

Node root=new node(1);

root.left=newnode(2);

root.right=newnode(3);

root.left.right=newnode(4);

leverOrder(root);

}

Here the time complexity will be O(n)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.