import java.util.*;
import java.lang.*;
import java.io.*;

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, String 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, "");
}

}

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);
    tst.put("The",7);
    tst.traverse();

}

}

class Node {

public char character;
public Node left, right, middle;
public int value;

public Node(char character) {
    this.character = character;
}
}