Implement the following method in BST.java that returns the keys in level order
ID: 3818487 • Letter: I
Question
Implement the following method in BST.java that returns the keys in level order (in order of their distance from the root, with nodes on each level in order from left to right). Hint: Study keys(..) method in term of how to return an iterable instance. Use a Queue for traversal. public Iterable KeysInLevelOrder()
public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node node, Queue<Key> queue, Key lo, Key hi) {
if (node == null)
return;
int cmplo = lo.compareTo(node.key);
int cmphi = hi.compareTo(node.key);
if (cmplo < 0)
// if lo < node.key, visit left subtree
keys(node.left, queue, lo, hi);
if (cmplo <= 0 && cmphi >= 0)
// if node.key within range, add to the queue
queue.add(node.key);
if (cmphi > 0)
// if hi > node.key, visit right subtree
keys(node.right, queue, lo, hi);
}
Explanation / Answer
import java.util.LinkedList;
import java.util.Queue;
// Recursive Java program for level order traversal of Binary Search Tree
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BST
{
// Root of the Binary Tree
Node root;
public BST()
{
root = null;
}
/* function to print level order traversal of tree*/
public Iterable KeysInLevelOrder()
{
int h = height(root);
int i;
Queue<Node> q = new LinkedList<>();
for (i=1; i<=h; i++)
getGivenLevel(root, i, q);
return q;
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node root)
{
if (root == null)
return 0;
else
{
/* compute height of each subtree */
int lheight = height(root.left);
int rheight = height(root.right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
void getGivenLevel (Node root ,int level, Queue<Node> q)
{
if (root == null)
return;
if (level == 1){
q.add(root);
}
else if (level > 1)
{
getGivenLevel(root.left, level-1, q);
getGivenLevel(root.right, level-1, q);
}
}
/* Driver program to test above functions */
public static void main(String args[])
{
BST tree = new BST();
tree.root= new Node(1);
tree.root.left= new Node(2);
tree.root.right= new Node(3);
tree.root.left.left= new Node(4);
tree.root.left.right= new Node(5);
System.out.println("Level order traversal of binary tree is ");
Iterable<Node> queue = tree.KeysInLevelOrder();
for(Node n : queue)
{
System.out.println(n.data + " ");
}
}
}