Construct a binary tree from in-order and level order traversals

Given in-order and level-order traversals of a Binary Tree, the task is to construct the Binary Tree and return its root.

Example:

Input: in[] = {4, 8, 10, 12, 14, 20, 22}; level[] = {20, 8, 22, 4, 12, 10, 14}; Output:

Answer

import java.util.*;

public class ConstructTreeFromInOrderAndLevelOrder {
    public Node createTree(int[] in, int[] lvl, int n) {
        if (n == 0)
            return null;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++)
            map.put(in[i], i);
        // Root
        Node tree = new Node(lvl[0]);
        Queue<pair> q = new LinkedList<>();
        int pointer = 1;
        q.add(new pair(tree, 0, n - 1));
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                pair x = q.poll();
                if (pointer == n)
                    continue;
                // Get index of current node in IN-ORDER array
                int index = map.get(x.node.val);
                // Get index of the next level order node in IN-ORDER array
                int leftPos = map.get(lvl[pointer]);
                // If this node fits within our area of sub-tree
                // Then this node will definitely be the head of that sub-tree
                // because it is the first one in level order from that sub-tree
                if (leftPos >= x.L && leftPos < index) {
                    x.node.left = new Node(lvl[pointer]);
                    q.add(new pair(x.node.left, x.L, index - 1));
                    pointer++;
                }
                int rightPos = map.get(lvl[pointer]);
                if (rightPos > index && rightPos <= x.R) {
                    x.node.right = new Node(lvl[pointer]);
                    q.add(new pair(x.node.right, index + 1, x.R));
                    pointer++;
                }
            }
        }
        return tree;
    }

    static class Node {
        int val;
        Node left, right;

        Node(int x) {
            val = x;
        }
    }

    static class pair {
        Node node;
        // L & R define the area of a tree as indices of inorder array
        int L, R;

        pair(Node node, int L, int R) {
            this.node = node;
            this.L = L;
            this.R = R;
        }
    }
}