tree A ternary search tree is a type of tree that can have 3 nodes: a low child, an equal child, and a high child. Each node stores a single character and the tree itself is ordered the same way a binary search tree is, with the exception of a possible third node. Searching a ternary search tree involves passing in a string to test whether any path contains it. The time complexity for searching a balanced ternary search tree is O(log n). Searching algorithms Searching for a specific key Assuming the tree is ordered, we can take a key and attempt to locate it within the tree. The following algorithms are generalized for binary search trees, but the same idea can be applied to trees of other formats. Recursive search-recursive(key, node) if node is NULL return EMPTY_TREE if key < node.key return search-recursive(key, node.left) else if key > node.key return search-recursive(key, node.right) else return node Iterative searchIterative(key, node) currentNode := node while currentNode is not NULL if currentNode.key = key return currentNode else if currentNode.key > key currentNode := currentNode.left else currentNode := currentNode.right Searching for min and max In a sorted tree, the minimum is located at the node farthest left, while the maximum is located at the node farthest right. Minimum findMinimum(node) if node is NULL return EMPTY_TREE min := node while min.left is not NULL min := min.left return min.key Maximum findMaximum(node) if node is NULL return EMPTY_TREE max := node while max.right is not NULL max := max.right return max.key See also Trie Binary tree Depth-first search References Search trees Search algorithms