Editing Binary search tree (section)

====Iterative search====
The recursive version of the search can be "unrolled" into a [[while loop]]. On most machines, the iterative version is found to be more [[Computer performance|efficient]].<ref name="algo_cormen" />{{rp|291}}
{|
|- style="vertical-align:top"
|
 Iterative-Tree-Search(x, key)
     '''while''' x &ne; NIL '''and''' key &ne; x.key '''do'''
         '''if''' key < x.key '''then'''
             x := x.left
         '''else'''
             x := x.right
         '''end if'''
     '''repeat'''
     '''return''' x
|}
Since the search may proceed till some [[leaf node]], the running time complexity of BST search is <math>O(h)</math> where <math>h</math> is the [[Tree (data structure)#Terminology|height of the tree]]. However, the worst case for BST search is <math>O(n)</math> where <math>n</math> is the total number of nodes in the BST, because an unbalanced BST may degenerate to a linked list. However, if the BST is [[height-balanced tree|height-balanced]] the height is <math>O(\log n)</math>.<ref name="algo_cormen" />{{rp|290}}