class TrieNode 
{
    char letter;
	int  intvalue;
	
	TrieNode next; // next node on same level  // sibling
	TrieNode link; // link to next level       // child
	
    public TrieNode(int i, char l)
	{	letter = l;
		intvalue = i;
    }

	public void printNode(String message)
	{	System.out.println(intvalue + " " + letter +  " link=" + link + " next=" + next + " " + message);
	}
	public String returnNode(String message)
	{	return(intvalue + " " + letter + " " + " link=" + link + " next=" + next + " " + message);
	}
 
} // end class TrieNode

public class Trie 
{	TrieNode root;
	TrieNode current;
	int nextNodeNumber = 0;

    public Trie()
	{	root = new TrieNode(nextNodeNumber, '-' ); // 0, <>
		root.next = null;
		nextNodeNumber++;
	}
	
	public void printTrie()
	{	System.out.println("TRIE");
		inorder(root);
	}
	
	private void inorder(TrieNode currentNode)
	{
	 if(currentNode.link != null) inorder(currentNode.link);  
	 System.out.println( currentNode + " " + currentNode.returnNode(""));  
	 if(currentNode.next != null) inorder(currentNode.next); 
	}
	
	
	public TrieNode head()
	{	return root;
	}
	
	public TrieNode isChild(TrieNode currentNode, char letter)
	{	if(currentNode.link == null)	return null;
		currentNode = currentNode.link;
		while(true)
		{	if(currentNode.letter == letter)	return currentNode;
			else if(currentNode.next == null)	return null;
			else currentNode = currentNode.next;
		}
	}
	
	
	public TrieNode addNode(TrieNode currentNode, char l)
	{	TrieNode newNode = new TrieNode(nextNodeNumber, l);
		
		if(currentNode.link == null)
		{	currentNode.link = newNode;
		}
		else
		{	currentNode = currentNode.link;
			while(true)
			{	if(currentNode.next == null)	break;
				else currentNode = currentNode.next;
			}
			currentNode.next = newNode;
		}
		
		//newNode.printNode("Added");
		nextNodeNumber++;
		
		return newNode;
	}
	
}	// end class Trie