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

public int[] getDistanceFromRoot(Node head,int[] arr){
        int[] result = new int[arr.length];
        Arrays.fill(result,-1);
        Map<Integer,Integer> map = new HashMap<>();
        for(int j =0; j<arr.length;j++){
            map.putIfAbsent(arr[j],j);
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        int level =0;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                Node temp = queue.poll();
                if(map.containsKey(temp.val) && result[map.get(temp.val)]==-1){
                    result[map.get(temp.val)]= level;
                }
                if(temp.left !=null)
                    queue.add(temp.left);
                if(temp.right !=null)
                    queue.add(temp.right);
                size--;
            }
            level++;
        }
        return result;
    }