Ternary Search Tries TST - Java Implementation

Ternary search tries are similar to R-way tries but more space efficient.

TST Performance:

Search hit         :   L+ln N
Search miss        :   ln N
Insert             :   L + ln N
Space (references) :   4 N + R^2

Source - Keys are strings, values are generic:

public class TST<T> {
    class Node{
        char c;
        T v;
        Node left, mid, right;
        
        Node(){}
        Node(char c){this.c = c;}
        Node(T v){this.v = v;}
        Node(char c, T v){this.c = c;this.v = v;}
    }
    
    Node root; 
    
    public void add(String s, T value){
       System.out.println("\nAdding ["+s+" : "+value+"]");
       root = add(root, s, 0, value);
    }
    
    private Node add(Node n, String s, int i, T value){ 
        System.out.println("Adding "+s.charAt(i));
        if(n==null){
            System.out.println("Creating new node for "+s.charAt(i));
            n = new Node(s.charAt(i));
            if(i==s.length()-1){n.v = value; return n;}
        }
        if(s.charAt(i)==n.c){
            if(i==s.length()-1){System.out.println("Overwriting ");n.v = value; return n;}
            System.out.println("Going down from node "+n.c);
            n.mid = add(n.mid, s, i+1, value);
        }
        else if(s.charAt(i)<n.c){
            System.out.println("Going left from node "+n.c);
            n.left = add(n.left, s, i, value);
        }
        else{
            System.out.println("Going right from node "+n.c);
            n.right = add(n.right, s, i, value);
        }
        return n;
    }
    
    public boolean findKey(String s){ 
        System.out.println("\nFinding key ["+s+"] root = "+root.c);
        return findKey(root, s, 0); 
    }
    
    private boolean findKey(Node n, String s, int i){  
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){

                System.out.println("Last node found: "+n.c+" Checking the presence of a value");
                if(n.v!=null){System.out.println(n.v); return true;} 
                else {
                    System.out.println("n.v was null n.v = "+n.v);
                    return false;
                }
            }
        }else if(i>s.length())return false; 
        if(s.charAt(i)==n.c){
            System.out.println("Going down from node "+n.c);
            return findKey(n.mid, s, i+1);
        }
        else if(s.charAt(i)<n.c){
            System.out.println("Going left from node "+n.c);
            return findKey(n.left, s, i);
        }
        else {
            System.out.println("Going right from node "+n.c);
            return findKey(n.right, s, i);
        }        
    }
    
    public void delete(String s){
        System.out.println("\n\nDeleting key "+s+":\n");
        delete(root, s, 0);
    }
    
    private boolean delete(Node n, String s, int i){
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){

                System.out.println("Last node found: "+n.c+" Checking the presence of a value");
                if(n.v!=null){System.out.println("Deleting "+n.c+" : "+n.v); n.v = null;return true;}
                else {
                    System.out.println("n.v was null n.v = "+n.v);
                    return false;
                }
            }
        }else if(i>s.length())return false; 
        
        boolean r;
        if(s.charAt(i)==n.c){
            System.out.println("Going down from node "+n.c);
            if((r=delete(n.mid, s, i+1))){ 
                if(n.mid.v == null && n.mid.left == null && n.mid.mid == null && n.mid.right == null){
                    System.out.println("Setting "+n.c+" node's mid to null");
                    n.mid = null;
                }
            }
        }
        else if(s.charAt(i)<n.c){
            System.out.println("Going left from node "+n.c);
            if((r=delete(n.left, s, i))){ 
                if(n.left.v == null && n.left.left==null && n.left.mid == null && n.left.right == null){
                    System.out.println("Setting "+n.c+" node's left to null");
                    n.left = null;
                }
            }
        }
        else{
            System.out.println("Going right from node "+n.c);
            
            if((r=delete(n.right, s, i))){ 
                if(n.right.v == null && n.right.left == null && n.right.mid == null && n.right.right == null){
                    System.out.println("Setting "+n.c+" node's right to null");
                    n.right = null;
                }
            } 
        }
        return r;
    }
    
    public static void main(String[] args){
        TST<Integer> tst = new TST<>();
        String s = "she sells seashells by the sea the shells she sells are surely seashells";
        String a[] = s.split(" ");
        
        int i = 0;
        for(String ss:a){
            tst.add(ss, i++);
        }
        
        tst.findKey("seashells");
        tst.findKey("seashell");
        tst.findKey("z");
        tst.delete("seashell");
        tst.delete("seashells");
        tst.findKey("seashells");     
        tst.findKey("sea");
    }
}

Output:

Adding [she : 0]
Adding s
Creating new node for s
Going down from node s
Adding h
Creating new node for h
Going down from node h
Adding e
Creating new node for e

Adding [sells : 1]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Creating new node for e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding l
Creating new node for l
Going down from node l
Adding s
Creating new node for s

Adding [seashells : 2]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding a
Going left from node l
Adding a
Creating new node for a
Going down from node a
Adding s
Creating new node for s
Going down from node s
Adding h
Creating new node for h
Going down from node h
Adding e
Creating new node for e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding l
Creating new node for l
Going down from node l
Adding s
Creating new node for s

Adding [by : 3]
Adding b
Going left from node s
Adding b
Creating new node for b
Going down from node b
Adding y
Creating new node for y

Adding [the : 4]
Adding t
Going right from node s
Adding t
Creating new node for t
Going down from node t
Adding h
Creating new node for h
Going down from node h
Adding e
Creating new node for e

Adding [sea : 5]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding a
Going left from node l
Adding a
Overwriting 

Adding [the : 6]
Adding t
Going right from node s
Adding t
Going down from node t
Adding h
Going down from node h
Adding e
Overwriting 

Adding [shells : 7]
Adding s
Going down from node s
Adding h
Going down from node h
Adding e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding l
Creating new node for l
Going down from node l
Adding s
Creating new node for s

Adding [she : 8]
Adding s
Going down from node s
Adding h
Going down from node h
Adding e
Overwriting 

Adding [sells : 9]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding l
Going down from node l
Adding l
Going down from node l
Adding s
Overwriting 

Adding [are : 10]
Adding a
Going left from node s
Adding a
Going left from node b
Adding a
Creating new node for a
Going down from node a
Adding r
Creating new node for r
Going down from node r
Adding e
Creating new node for e

Adding [surely : 11]
Adding s
Going down from node s
Adding u
Going right from node h
Adding u
Creating new node for u
Going down from node u
Adding r
Creating new node for r
Going down from node r
Adding e
Creating new node for e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding y
Creating new node for y

Adding [seashells : 12]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding a
Going left from node l
Adding a
Going down from node a
Adding s
Going down from node s
Adding h
Going down from node h
Adding e
Going down from node e
Adding l
Going down from node l
Adding l
Going down from node l
Adding s
Overwriting 

Finding key [seashells] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Going down from node l
Last node found: s Checking the presence of a value
12

Finding key [seashell] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Last node found: l Checking the presence of a value
n.v was null n.v = null

Finding key [z] root = s
Going right from node s
Going right from node t


Deleting key seashell:

Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Last node found: l Checking the presence of a value
n.v was null n.v = null


Deleting key seashells:

Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Going down from node l
Last node found: s Checking the presence of a value
Deleting s : 12
Setting l node's mid to null
Setting l node's mid to null
Setting e node's mid to null
Setting h node's mid to null
Setting s node's mid to null
Setting a node's mid to null

Finding key [seashells] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a

Finding key [sea] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Last node found: a Checking the presence of a value
5