Editing Search tree (section)

===Binary search tree===
{{Main|Binary search tree}}
A Binary Search Tree is a node-based data structure where each node contains a key and two subtrees, the left and right. For all nodes, the left subtree's key must be less than the node's key, and the right subtree's key must be greater than the node's key. These subtrees must all qualify as binary search trees.

The worst-case [[time complexity]] for searching a binary search tree is the [[Tree (data structure)#Terminology used in trees|height of the tree]], which can be as small as O(log n) for a tree with n elements.