// // Purpose: // // Return a list of all the key/value Entrys stored in the tre

Question

//
   // Purpose:
   //
   // Return a list of all the key/value Entrys stored in the tree
   // The list will be constructed by performing a level-order
   // traversal of the tree.
   //
   // Level order is most commonly implemented using a queue of nodes.
   //
   // From wikipedia (they call it breadth-first), the algorithm for level order is:
   //
   //   levelorder()
   //       q = empty queue
   //       q.enqueue(root)
   //       while not q.empty do
   //           node := q.dequeue()
   //           visit(node)
   //           if node.left != null then
   //           q.enqueue(node.left)
   //           if node.right != null then
   //           q.enqueue(node.right)
   //
   // Note that we will use the Java LinkedList as a Queue by using
   // only the removeFirst() and addLast() methods.
   //
   public List> entryList() {
       List> l = new LinkedList>();

return l;

}

Explanation / Answer

import java.util.LinkedList;
import java.util.List;

/* 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;
}
}

class BinaryTree
{
// Root of the Binary Tree
Node root;

public BinaryTree()
{
root = null;
}

// Given a binary tree. Return its nodes in a list in level order traversal
public List<Node> entryList()
{
LinkedList<Node> queue = new LinkedList<>();
List<Node> l = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty())
{
Node tempNode = queue.removeFirst();
l.add(tempNode);

/*Enqueue left child */
if (tempNode.left != null) {
queue.addLast(tempNode.left);
}

/*Enqueue right child */
if (tempNode.right != null) {
queue.addLast(tempNode.right);
}
}
return l;
}

/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
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);
  
List<Node> l = tree.entryList();

System.out.println("Level order traversal of binary tree via obtained list ");
for(Node n: l)
{
System.out.print(n.data + "->");
}
System.out.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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