more characters in the key then the first character of the key must be removed and a recursive call is made given the equal kid node and the modified key. This can also be written in a non-recursive way by using a pointer to the current node and a pointer to the current character of the key. Pseudocode function search(string query) is if is_empty(query) then return false node p := root int idx := 0 while p is not null do if query[idx] < p.splitchar then p := p.left else if query[idx] > p.splitchar then p := p.right; else if idx = length(query) then return true idx := idx + 1 p := p.mid return false Deletion The delete operation consists of searching for a key string in the search tree and finding a node, called firstMid in the below pseudocode, such that the path from the middle child of firstMid to the end of the search path for the key string has no left or right children. This would represent a unique suffix in the ternary tree corresponding to the key string. If there is no such path, this means that the key string is either fully contained as a prefix of another string, or is not in the search tree. Many implementations make use of an end of string character to ensure only the latter case occurs. The path is then deleted from firstMid.mid to the end of the search path. In the case that firstMid is the root, the key string must have been the last string in the tree, and thus the root is set to null after the deletion. function delete(string key) is if is_empty(key) then return node p := root int idx := 0 node firstMid := null while p is not null do if key[idx] < p.splitchar then firstMid := null p := p.left else if key[idx] > p.splitchar then firstMid := null p := p.right else firstMid := p while p is not null and key[idx] == p.splitchar do idx := idx + 1 p := p.mid if firstMid == null then return // No unique string suffix // At this point, firstMid points to the node before the strings unique suffix occurs node q := firstMid.mid node p := q firstMid.mid := null // disconnect suffix from tree while q is not null do //walk down suffix path and delete nodes