package udo.logic;

import java.util.List;

public class TernarySearchTree {
    public static class Node {
        private char myChar;
        private Node left, right, center;
        private Boolean isWordEnd;
        
        public Node(char myChar, Boolean isWordEnd) {
            this.myChar = myChar;
            this.isWordEnd = isWordEnd;
        }
    }
    
    private Node root = null;
    
    private Node add(String s, Integer index, Node node) {
        if (node == null) {
            node = new Node(s.charAt(index), false);
        }
        
        if (s.charAt(index) < node.myChar) {
            node.left = add(s, index, node.left);
        } else if (s.charAt(index) > node.myChar) {
            node.right = add(s, index, node.right);
        } else {
            if (index + 1 == s.length()) {
                node.isWordEnd = true;
            } else {
                node.center = add(s, index + 1, node.center); 
            }
        }
        
        return node;
    }
    
    public void add(String s) {
        if (s == null) {
            return;
        }
        
        s = s.trim();
        if (s.equalsIgnoreCase("")) {
            return;
        }
        
        root = add(s, 0, root);
    }
    
    public List<String> searchPrefix(String prefix, Integer numWords) {
        int index = 0;
        Node curNode = root;
        
        while (curNode != null) {
            if (index == prefix.length()) {
                return searchTree(curNode, numWords);
            }
            
            if (prefix.charAt(index) < curNode.myChar) {
                curNode = curNode.left;
            } else if (prefix.charAt(index) > curNode.myChar) {
                curNode = curNode.right;
            } else {
                index++;
                curNode = curNode.center;
            }
        }
        
        return null;
    }
    
    public List<String> searchPrefix(String prefix) {
        return searchPrefix(prefix, null);
    }
    
    /**
     * Find words in the tree rooted at some node
     * @param node the root of the tree for the search
     * @param numWords maximum number of words to search for or
     *                 search for all words if this is null
     * @return list of found words
     */
    private List<String> searchTree(Node node, Integer numWords) {
        return null;
    }

    public static void main(String[] args) {
        
    }

}

@@ -13,16 +13,44 @@
 logic;%0A%0A
+import java.util.ArrayList;%0A
 import j
@@ -99,29 +99,32 @@
 Tree %7B%0A    p
-ublic
+rotected
  static clas
@@ -213,21 +213,23 @@
       pr
-ivate
+otected
  Boolean
@@ -1529,16 +1529,23 @@
 (curNode
+.center
 , numWor
@@ -2390,35 +2390,1283 @@
 ) %7B%0A        
-return null
+List%3CCharacter%3E curWord = new ArrayList%3C%3E();%0A        List%3CString%3E result = new ArrayList%3C%3E();%0A        %0A        searchTreeHelper(node, numWords, curWord, result);%0A        %0A        return result;%0A    %7D%0A%0A    private void searchTreeHelper(Node node, Integer numWords,%0A                                  List%3CCharacter%3E curWord,%0A                                  List%3CString%3E result) %7B%0A        if (numWords != null && result.size() == numWords) %7B%0A            return;%0A        %7D%0A        if (node == null) %7B%0A            return;%0A        %7D%0A        %0A        searchTreeHelper(node.left, numWords, curWord, result);%0A        if (numWords != null && result.size() == numWords) %7B%0A            return;%0A        %7D%0A%0A        curWord.add(node.myChar);%0A%0A        if (node.isWordEnd) %7B%0A            result.add(charListToString(curWord));%0A        %7D%0A        searchTreeHelper(node.center, numWords, curWord, result);%0A        %0A        curWord.remove(curWord.size() - 1);%0A%0A        searchTreeHelper(node.right, numWords, curWord, result);%0A    %7D%0A%0A    private String charListToString(List%3CCharacter%3E curWord) %7B%0A        StringBuilder builder = new StringBuilder(curWord.size());%0A%0A        for (char c : curWord) %7B%0A            builder.append(c);%0A        %7D%0A        %0A        return builder.toString()
 ;%0A    %7D%0A%0A   

Complete code for the ternary search tree