CareerCup

Level order bfs

use bfs/level order traversal while keeping track of a distance from a root. If the first occurence of each number of the given array is found, update the result array with the current distance.
time O(n) where n is the total number of nodes in a tree
space O(Math.max(k, n)) where k is the total number of elements in an array.

public static int[] getDistanceFromRoot(Node head, int[] arr) {
 int[] result = new int[arr.length];
 for (int i = 0; i < result.length; ++i) {
  result[i] = -1;
 }

 HashMap<Integer, Integer> hm = new HashMap<>();
 for (int j = 0; j < arr.length; ++j) {
  hm.put(arr[j], j);
 }

 Queue<Node> q = new LinkedList<>();
 q.add(head);
 int level = 0;

 while (!q.isEmpty()) {
  int size = q.size();
  while (size > 0) {
   Node temp = q.remove();
   if (hm.containsKey(temp.val) && result[hm.getValue(temp.val)] == -1) {
    result[hm.get(temp.val)] = level;
   }

   --size;
  }
  ++level;
 }

 return result;
}