Question

Question B1 You are given the following Java classes: public class Queue { private static class Node { Object object; Node next; Node () { object = null; next = null; } Node (Object object, Node next) { this.object = object; this.next = next; private Node header; private int size = 0; // size shows the no of elements in queue public Object dequeue () { if (size == 0 ) { return null; else { Object remove_object = header.object; header = header.next; size--; return remove_object; public void enqueue (Object object) { if (size == 0) header = new Node (object, null); else { Node p = new Node (object, null); Node r = header; while (r.next != null) r = r.next; r.next = p; size++;

Answer 1

All the explanation is in the code comments. Hope this helps!

Code:

Queue.java (unchanged)

public class Queue
{
private static class Node {
Object object;
Node next;
Node() { object = null; next = null; }
Node(Object object, Node next) {
this.object = object;
this.next = next;
}
}
private Node header;
private int size = 0;
public Object dequeue() {
if(size == 0) {
return null;
} else {
Object remove_object = header.object;
header = header.next;
size--;
return remove_object;
}
}
public void enqueue(Object object) {
if(size == 0)
header = new Node(object, null);
else {
Node p = new Node(object, null);
Node r = header;
while(r.next != null)
r = r.next;
r.next = p;
}
size++;
}
}

BTNode.java (unchanged)

public class BTNode
{
int key;
BTNode left;
BTNode right;
public BTNode(int key) {
this.key = key;
}
}

BTNodeTree.java

public class BTNodeTree
{
public BTNode r;
  
// a) - function to print postOrder of BST
public void postOrder(BTNode t) {
  
// base condition for null node
if(t==null)
return;
  
// call for the left child
postOrder(t.left);
// call for the right child
postOrder(t.right);
  
// now print the value at the node
System.out.print(t.key + " ");
}
  
// function to print level order traversal for BST
public void levelOrder(BTNode t) {
  
// return for empty tree
if(t==null)
return;
  
// create an empty queue for levelOrder traversal
Queue q = new Queue();
// put the root in queue
q.enqueue(t);
  
// pop the first element from queue
BTNode curr = (BTNode) q.dequeue();
  
// loop till all elements are traversed
while(curr != null) {
  
// Pushing left child current node
if (curr.left != null)
q.enqueue(curr.left);

// Pushing right child current node
if (curr.right != null)
q.enqueue(curr.right);
  
// print the present node value
System.out.print(curr.key + " ");
  
// move to next node
curr = (BTNode) q.dequeue();
}
}
  
// b) - funtion to insert values in BST
public void insert(int theKey, BTNode t) {
  
// for null tree root
if(t==null) {
t = new BTNode(theKey);
return;
}
  
// insert at the left half
if(theKey < t.key) {
if(t.left == null)
t.left = new BTNode(theKey);
else insert(theKey, t.left);
}
// else insert in the right
else {
if(t.right == null)
t.right = new BTNode(theKey);
else insert(theKey, t.right);
}
}
  
// c) - recursive function to return the height of tree
public int height(BTNode t) {
  
// end of tree
if(t == null)
return 0;
  
// add present height and maximum of the heights of the 2 children
return 1 + Math.max(height(t.left), height(t.right));
}
}

Main.java (driver class)

// driver class to test the program
public class Main
{
public static void main(String[] args)
{
// sample run
BTNodeTree ob = new BTNodeTree();
BTNode root = new BTNode(19);
ob.insert(22, root);
ob.insert(15, root);
ob.insert(7, root);
ob.insert(35, root);
ob.insert(18, root);
ob.insert(30, root);

// part a)
System.out.print("PostOrder traversal: ");
ob.postOrder(root);
System.out.println();

// print height for part c)
System.out.println("Height of tree: " + ob.height(root));

// for level order, the tree should print like this -
// 19 15 22 7 18 35 30
System.out.print("LevelOrder traversal: ");
ob.levelOrder(root);
System.out.println();
}
}

Sample output:

Postorder traversal: 7 18 15 30 35 22 19 Height of tree: 4 LevelOrder traversal: 19 15 22 7 18 35 30

Code screenshots (only for changed code):

BTNodeTree.java

1 public class BTNodeTree public BTNode r; // a) - function to print postOrder of BST public void postOrder (BTNode t) { // base condition for null node if(t==null) return; 9. 10 11 // call for the left child postorder (t.left); // call for the right child postorder(t.right); 12 13 14 15 16 // now print the value at the node 17 System.out.print(t.key + "); 18 19 20 // function to print level order traversal for BST public void levelOrder (BTNode t) { 22 - 23 // return for empty tree if(t==null) 24 25 26 return; 27 // create an empty queue for levelorder traversal 28 new Queue(); 29 Queue q // put the root in queue q. enqueue(t); 30 31 32 // pop the first element from queue BTNode curr = 33 (BTNode) q.dequeue(); 34 35 // Loop tiLl all elements are traversed while(curr != null) { 36 37 38 // Pushing left child current node if (curr.left != null) 39 40

q. enqueue (curr.left); 41 42 // Pushing right child current node if (curr.right != null) q. enqueue (curr.right); 43 44 45 46 // print the present node value System.out.print(curr.key + " "); 47 48 49 // move to next node 50 (BTNode) q.dequeue (); 51 curr = 52 53 54 // b) - funtion to insert values in BST public void insert(int thekey, BTNode t) { 55 56- 57 // for nullL tree root if(t==null) { t = new BTNode (thekey); 58 59- 60 61 return; } 62 63 // insert at the left half if(thekey < t.key) { if(t.left t.left = new BTNode(thekey); else insert(theKey, t.left); 64 65 null) 66 67 68 69 // else insert in the right else { if(t.right t.right else insert(theKey, t.right); 70 71- null) = new BTNode (thekey); 72 73 74 75 76 77 // c) public int height(BTNode t) { - recursive function to return the height of tree 78 79- 80

// end of tree 81 null) if(t 82 =3= return 0; 83 84 // add present height and maximum of the heights of the 2 children 85 return 1 + Math.max(height(t.left), height(t.right)); 86 87 88 }

Main.java

1 // driver class to test the program 2 public class Main 3- { public static void main(String[] args) { // sample run BTNodeTree ob - new BTNodeTree (); BTNode root = new BTNode(19); ob.insert(22, root); ob.insert(15, root); ob.insert(7, root); ob.insert(35, root); ob.insert(18, root); ob.insert(30, root); 4 8. 9. 10 11 12 13 14 15 // part a) System.out.print("Postorder traversal: "); ob.postorder(root); System.out.println(); 16 17 18 19 20 // print height for part c) System.out.println("Height of tree: 21 + ob.height(root)); 22 23 // for Level order, the tree should print like this // 19 15 22 7 18 35 30 System.out.print("Level0rder traversal: "); ob.levelorder(root); System.out.println(); 24 25 26 27 28 29 30 }