I have a Ternary Search Tree (Trie) and I want to print out all of the words in it.
How do I go about this using this current implementation that I have below?
I have a standard put
method to add new words to the tree. I was attempting to print the words using an in-order traversal, but I'm unsure how exactly to complete the function.
class TST {
private Node root;
public void put(String key, int value) {
root = put(root, key, value, 0);
}
private Node put(Node node, String key, int value, int index) {
char c = key.charAt(index);
if( node == null ){
node = new Node(c);
}
if( c < node.character ){
node.left = put(node.left, key, value, index);
}else if( c > node.character ){
node.right = put(node.right, key, value, index);
}else if( index < key.length()-1 ){
node.middle = put(node.middle, key, value, index+1);
}else{
node.value = value;
}
return node;
}
public Integer get(String key) {
Node node = get(root, key, 0);
if (node == null) {
return null;
}
return node.value;
}
public Node get(Node node, String key, int index) {
if(node == null) {
return null;
}
char c = key.charAt(index);
if (c < node.character) {
return get(node.left, key, index);
} else if (c > node.character) {
return get(node.right, key, index);
} else if(index < key.length() -1) {
return get(node.middle, key, index);
} else {
return node;
}
}
public void inorderTraversal(Node node) {
System.out.print(node.character + ":" + node.value + " ");
if(node.left != null) {
inorderTraversal(node.left);
}
if(node.middle != null) {
inorderTraversal(node.middle);
}
if(node.right != null) {
inorderTraversal(node.right);
}
}
public void traverse() {
inorderTraversal(root);
}
}
public class Main {
public static void main(String[] args) {
TST tst = new TST();
tst.put("This",3);
tst.put("There",4);
tst.put("Them",5);
tst.put("High",6);
System.out.println(tst.get("T"));
tst.traverse();
}
}
class Node {
public char character;
public Node left, right, middle;
public int value;
public Node(char character) {
this.character = character;
}
}
Since each node only stores a single character, you need to pass along a String (or StringBuilder, if you're trying to be efficient) representing the prefix defined by the path from the root when doing your traversal.
As per the definition of a ternary search tree, you should only append to this prefix when going to the middle node.
An example implementation:
public void inorderTraversal(Node node, String word) {
// handle end of word
if (node.value != 0) {
System.out.println(word + node.character + ": " + node.value);
}
if(node.left != null) {
inorderTraversal(node.left, word);
}
if (node.middle != null) {
inorderTraversal(node.middle, word + node.character);
}
if(node.right != null) {
inorderTraversal(node.right, word);
}
}
public void traverse() {
inorderTraversal(root, "");
}
Demo.
It's also possible to store the String representing the full word at each node during construction, since you already have the complete word in your put
method (if you're not worried about the memory usage).
Note that this / your code doesn't allow for mapping words to a 0 value - one way to deal with that is to use Integer
instead of int
, then you can use != null
to check for the end of a word.