(Hacker Rank) Veronica Mars and the Binary Search Tree - Solution

Link to the problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/mars-and-the-binary-search-tree

Using a simple Binary Search Tree could imply in an execution time of O(10^9) in the worst case. Then, a TreeMap structure was used to keep the indexes of the nodes already inserted, which helped to know the location of the new node to be inserted.


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static Node root;
    public static long mod = (long)Math.pow(10, 9)+7;

    public static Node insert(Node n, long value) {
        if (root == null) {
            root = new Node(null, null, null, value, 1);
            return root;
        }
        else {
            Node currNode = n;
            Node parentCurrNode = null;
            long key = n.key;
            while (currNode != null) {
                parentCurrNode = currNode;               
                if (currNode.value < value) {
                    currNode = currNode.rightChild;
                    key = 2*key+1;
                }
                else {
                    currNode = currNode.leftChild;
                    key = 2*key;
                }
                key = key%mod;
            }
            currNode = new Node(parentCurrNode, null, null, value, key);
            if (currNode.value < parentCurrNode.value) {
                parentCurrNode.leftChild = currNode;
            }
            else {
                parentCurrNode.rightChild = currNode;
            }
            return currNode;
        }
       
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        root = null;
       
        TreeMap<Long, Node> map = new TreeMap<Long, Node>();
       
        int numNodes = Integer.parseInt(br.readLine());
        long[] nodes = new long[numNodes];
        String line = br.readLine();
        String[] s = line.split("\\s");
        nodes[0] = Long.parseLong(s[0]);
        Node n = insert(null, nodes[0]);
        map.put(nodes[0], n);
        bw.write(n.key + " ");
        for (int i = 1; i < numNodes; i++) {
            nodes[i] = Long.parseLong(s[i]);
            Map.Entry<Long,Node> ceil = map.ceilingEntry(nodes[i]);
            Map.Entry<Long,Node> floor = map.floorEntry(nodes[i]);
            if (ceil != null && ceil.getValue().leftChild == null) {
                n = insert(ceil.getValue(), nodes[i]);   
            }
            else {
                n = insert(floor.getValue(), nodes[i]);
            }
            map.put(nodes[i], n);
            if (i == numNodes-1) {
                bw.write(n.key + "\n");
            }
            else {
                bw.write(n.key + " ");
            }
        }
       
        bw.flush();
        bw.close();
    }
   
}

class Node {
    Node parent;
    Node leftChild;
    Node rightChild;
    long value;
    long key;
   
    public Node(Node p, Node l, Node r, long v, long k) {
        parent = p;
        leftChild = l;
        rightChild = r;
        value = v;
        key = k;
    }
}