import java.util.UUID;
import java.util.List;
import java.util.LinkedList;
import java.util.Map;


// implements prefix free trie
public class Trie {
    private static final char SENTINEL = 0d;
    private Node root = new InnerNode(); 
    
    public void insert(String s) {
        checknull(s);
        Node t = root;
        int j = 0;
        while (j < s.size() && t.child(s.charAt(j) != null) {
            t = t.child(s.charAt(j)); 
            j++;
        }   
        while (j < s.size()) {
            Node u = new InnerNode();
            t.addChild(s.charAt(j);
            t = u;
            j++;
        }

        Node u = new Sentinel();
        t.addChild(SENTINEL, u);
    }

    public boolean lookup(String s) {
        checknull(s);
        Node t = root;
        int j = 0;
        while (j < s.size() && t.child(s.charAt(j) != null) {
            t = t.child(s.charAt(j));
            j++;
        }
        if (j == s.size()) {
            return t.child(SENTINEL) != null;   
        }
        return false;
    }


    void checknull(String s) {
        if (s == null s.isEmpty() {
            throw new NullPointerException("String null or empty");
        }
    }

    private interface Node {
        Node child(char c);
        void addchild(char c, Node t);
    }

    private class InnerNode implements Node {
        final Map<Character, Node> childMap = new TreeMap<Character, Node>(); // check sync needed
        Node child(char c) {
            return childMap.get(c);
        } 
        void addChild(char c, Node t) {
            childMap.put(c, t);
        } 

    }

    private class Sentinel implements Node {
        final List<UUID> docids = new LinkedList();        
        void add(UUID docid) {
            docids.add(docid);
        }
    }
}

@@ -90,16 +90,42 @@
 il.Map;%0A
+import java.util.TreeMap;%0A
 %0A%0A// imp
@@ -211,17 +211,16 @@
 INEL = 0
-d
 ;%0A    pr
@@ -372,36 +372,38 @@
    while (j %3C s.
-size
+length
 () && t.child(s.
@@ -403,32 +403,33 @@
 hild(s.charAt(j)
+)
  != null) %7B%0A    
@@ -514,20 +514,22 @@
  (j %3C s.
-size
+length
 ()) %7B%0A  
@@ -598,16 +598,20 @@
 harAt(j)
+, u)
 ;%0A      
@@ -847,20 +847,22 @@
  (j %3C s.
-size
+length
 () && t.
@@ -878,16 +878,17 @@
 harAt(j)
+)
  != null
@@ -979,12 +979,14 @@
 = s.
-size
+length
 ()) 
@@ -1132,19 +1132,8 @@
 null
- s.isEmpty(
 ) %7B%0A
@@ -1187,21 +1187,18 @@
 ing 
-null or empty
+input null
 %22);%0A
@@ -1287,17 +1287,17 @@
 void add
-c
+C
 hild(cha
@@ -1462,32 +1462,39 @@
  needed%0A        
+public 
 Node child(char 
@@ -1545,32 +1545,39 @@
      %7D %0A        
+public 
 void addChild(ch
@@ -1764,16 +1764,19 @@
 void add
+doc
 (UUID do
@@ -1827,12 +1827,748 @@
   %7D%0A    
-%7D
+    public Node child(char c) %7B%0A            throw new UnsupportedOperationException();%0A        %7D%0A        public void addChild(char c, Node t) %7B%0A            throw new UnsupportedOperationException();%0A        %7D%0A    %7D%0A%0A%0A    public static void main(String %5B%5D args) %7B%0A        String%5B%5D doc = new String %5B%5D %7B%22pot%22, %22potato%22, %22pottery%22, %22tempo%22, %22tattoo%22%7D;%0A        Trie t = new Trie();%0A%0A        for (String s : doc) %7B%0A            t.insert(s);%0A        %7D%0A%0A        System.out.println(t.lookup(%22tempo%22));%0A        System.out.println(t.lookup(%22trie%22));%0A        System.out.println(t.lookup(%22%22));%0A        try %7B%0A            System.out.println(t.lookup(null));%0A            assert false;%0A        %7D%0A        catch (NullPointerException e) %7B%0A%0A        %7D%0A    %7D 
 %0A%7D%0A

Working trie. checks if string present in index