# Thoughts about optimal data structure for such problems and Java solution using a Binary Tree

• When I first read the problem, I could only think of a solution using Tree data structure. Albeit this is not the fastest solution for the given question. If we increase the year range to a large value and remove the limit on put/retrieve operations, will Tree be a better data structure over an array or an ArrayList?

'''
public class LogSystem {

``````TreeNode root;

class TreeNode {

class store{
int id;
String ts;

store(int id, String ts){
this.id = id;
this.ts = ts;
}
}

store info;
TreeNode left;
TreeNode right;

TreeNode(int id, String ts){
info = new store(id, ts);
left = null;
right = null;
}
}

public LogSystem() {
root = null;
}

public void put(int id, String timestamp) {
TreeNode pointer = root;

if(root == null){
root = new TreeNode(id, timestamp);
return;
}

while(pointer != null){
if(pointer.info.ts.compareTo(timestamp) < 0){
if(pointer.right == null){
pointer.right = new TreeNode(id, timestamp);
return;
}
pointer = pointer.right;
}
else{
if(pointer.left == null){
pointer.left = new TreeNode(id, timestamp);
return;
}
pointer = pointer.left;
}
}
}

public List<Integer> retrieve(String s, String e, String gra) {

TreeNode pointer = root;
List<Integer> list = new ArrayList<>();

if(gra.equals("Year"))
retrieveHelper(s.split(":"), e.split(":"), 0, root, list);

else if(gra.equals("Month"))
retrieveHelper(s.split(":"), e.split(":"), 1, root, list);

else if(gra.equals("Day"))
retrieveHelper(s.split(":"), e.split(":"), 2, root, list);

else if(gra.equals("Hour"))
retrieveHelper(s.split(":"), e.split(":"), 3, root, list);

else if(gra.equals("Minute"))
retrieveHelper(s.split(":"), e.split(":"), 4, root, list);

else if(gra.equals("Second"))
retrieveHelper(s.split(":"), e.split(":"), 5, root, list);

return list;
}

/* Level is the granularity in integer - 0: Year, 1: month, etc,. */
private void retrieveHelper(String[] start, String[] end, int level, TreeNode root, List<Integer> list){
if(root == null)
return;

int cur = 0; /* current level */

String[] strings = root.info.ts.split(":");

boolean moreThanStart = false;
boolean lessThanEnd = false;
boolean lessThanStart = false;
boolean moreThanEnd = false;
int cmp = 0;

while(cur <= level){

cmp = start[cur].compareTo(strings[cur]);
if(!lessThanStart && cmp < 0)
moreThanStart = true;

if(!moreThanStart && cmp > 0)
lessThanStart = true;

cmp = end[cur].compareTo(strings[cur]);
if(!moreThanEnd && cmp > 0){
lessThanEnd = true;
}
if(!lessThanEnd && cmp < 0)
moreThanEnd = true;

cur++;
}

if(moreThanEnd){
retrieveHelper(start, end, level, root.left, list);
return;
}

if(lessThanStart){
retrieveHelper(start, end, level, root.right, list);
return;
}