Question

Write a O(n) method valuesInLevelOrder() that returns a list of the nodes of a binary tree in level-order. That is, the method should return the root, then the nodes at depth 1, followed by the nodes at depth 2, and so on. Your algorithm should begin by putting the tree root on an initially empty queue. Then dequeue a node, add it to the output, and enqueue its left and right children (if they exist). Repeat until the queue is empty.

import java.util.*;

public class Node {
int data;
Node leftChild;
Node rightChild;
  
public Node(int data) {
this.data = data;
}
  
public Node(int data, Node leftChild, Node rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
  
public static List<Integer> valuesInLevelOrder(Node root) {
return null;
}

Answer 1

Refer to code below for the implementation of valuesInLevelOrder() that returns a list of the nodes of a binary tree in level-order

public static List<Integer> valuesInLevelOrder(Node root)
{
   Queue<Node> q = new LinkedList<Node>();
   int i = 0;
   List<Integer> levelOrder = new ArrayList<Integer>();
   q.add(root);
   while (!queue.isEmpty())
      {
        Node n = q.poll();
       levelOrder.add(i,n.data);
       i = i+1;

        if (n.left != null)
       {
            q.add(n.left);
        }

        if (n.right != null)
       {
            q.add(n.right);
        }
   }

   return levelOrder;
}