Editing Search tree (section)

==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.<ref>Gildea, Dan (2004). [http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf "Binary Search Tree"]</ref>

====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