/* example Trie structure
  
  -
 [0]
  |
 a|     d     b
 [1]---[2]---[4]
  |           |
 c|          a|     e     d
 [3]         [5]---[6]---[9]
              |
             d|     e
             [7]---[8]

*/


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

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

class Trie 
{	TrieNode root;
	TrieNode current;
	int		nextIndexNumber = 0;
	String	parentnodes = "";

    public Trie()
	{	root = new TrieNode(nextIndexNumber, '-' ); // 0, <>
		root.parent = null;
		root.next = null;
		nextIndexNumber++;
	}
	
	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 findNodeIndex(TrieNode currentNode, int i) {
		if (currentNode.index == i) {
			return currentNode;
		}

		if (currentNode.link != null) {
			TrieNode node = findNodeIndex(currentNode.link, i);
			if (node != null) {
				return node;
			}
		}

		if (currentNode.next != null) {
			TrieNode node = findNodeIndex(currentNode.next, i);
			if (node != null) {
				return node;
			}
		}

		return null;
	}
	
	public void traceBack(int i) {
		TrieNode currentNode = findNodeIndex(root, i);
		
		while(true) {
			parentnodes = parentnodes + currentNode.letter;
			currentNode = currentNode.parent;
			if(currentNode.parent == null) {
				break;
			}
		}
	}

	public TrieNode addNode(TrieNode currentNode, char l)
	{	TrieNode newNode = new TrieNode(nextIndexNumber, l);
		newNode.parent = currentNode;
		
		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;
		}
		
		nextIndexNumber++;
		
		return newNode;
	}
	
}	// end class Trie