Untitled

class Node{
    int val;
    Node left;
    Node right;
    Node(int v, Node l, Node r){
        val = v;
        left = l;
        right = r;
    }
}

class Solution {
    public ArrayList<Integer> order(ArrayList<Integer> A, ArrayList<Integer> B) {
        Map<Integer, Integer> hm = new HashMap<>();
        int n = A.size();
        for(int i = 0; i < n; i++){
            hm.put(A.get(i), B.get(i));
        }
        Collections.sort(A, Collections.reverseOrder());
        Node head = null;
        for(int i: A){
            head = addToTheLL(head, i, hm.get(i));
        }
        return getListFromLL(head);

    }

    Node addToTheLL(Node head, int value, int h){
        if(head == null){
            return new Node(value, null, null);
        }
        Node rootLeft = null;
        Node root = head;
        while(h --> 0){
            rootLeft = root;
            root = root.right;
        }
        if(rootLeft == null){
            return addToHead(head, root, value);
        }
        else if(root == null){
            return addToEnd(head, rootLeft, value);
        }
        else{
            return addInMiddle(head, root.left, root, value);
        }
    }
    
    Node addToHead(Node head, Node root, int val){
        root.left = new Node(val, null, root);
        return root.left;
    }
    
    Node addToEnd(Node head, Node root, int val){
        root.right = new Node(val, root, null);
        return head;
    }
    
    Node addInMiddle(Node head, Node root, Node rootRight, int val){
        Node valNode = new Node(val, root, rootRight);
        root.right = valNode;
        rootRight.left = valNode;
        return head;
    }
    
    ArrayList<Integer> getListFromLL(Node head){
        ArrayList<Integer> lst = new ArrayList<>();
        while(head != null){
            lst.add(head.val);
            head = head.right;
        }
        return lst;
    }
}