node and makes a recursive call on the appropriate node as in the lookup operation. If, however, the key's first character is equal to the node's value then the insertion procedure is called on the equal kid and the key's first character is pruned away. Like binary search trees and other data structures, ternary search trees can become degenerate depending on the order of the keys. Inserting keys in alphabetical order is one way to attain the worst possible degenerate tree. Inserting the keys in random order often produces a well-balanced tree. function insertion(string key) is node p := root //initialized to be equal in case root is null node last := root int idx := 0 while p is not null do //recurse on proper subtree if key[idx] < p.splitchar then last := p p := p.left else if key[idx] > p.splitchar then last := p p := p.right else: // key is already in our Tree if idx == length(key) then return //trim character from our key idx := idx+1 last := p p := p.mid p := node() //add p in as a child of the last non-null node (or root if root is null) if root == null then root := p else if last.splitchar < key[idx] then last.right := p else if last.splitchar > key[idx] then last.left := p else last.mid := p p.splitchar := key[idx] idx := idx+1 // Insert remainder of key while idx < length(key) do p.mid := node() p.mid.splitchar := key[idx] idx += 1 Search To look up a particular node or the data associated with a node, a string key is needed. A lookup procedure begins by checking the root node of the tree and determining which of the following conditions has occurred. If the first character of the string is less than the character in the root node, a recursive lookup can be called on the tree whose root is the lo kid of the current root. Similarly, if the first character is greater than the current node in the tree, then a recursive call can be made to the tree whose root is the hi kid of the current node. As a final case, if the first character of the string is equal to the character of the current node then the function returns the node if there are no more characters in the key. If there are