A binary search tree is a binary tree obeying the ordering invariant that, for every node, all keys in its left subtree are lesser (or lesser-or-equal, to admit duplicates) and all keys in its right subtree are greater, with the invariant holding recursively so that both subtrees are themselves binary search trees. This ordering lets a search discard an entire subtree at each comparison, reproducing binary search over a linked structure and yielding O(log n) search, insertion, and deletion in the average case — resolving the tension whereby unsorted arrays and linked lists give O(1) insertion but O(n) search, while sorted arrays give O(log n) search but O(n) insertion and deletion because of element shifting. Because the tree is built from links rather than contiguous storage, no shifting is required on update; the guarantee degrades to O(n) when the tree becomes unbalanced, so balance maintenance is the necessary condition for the logarithmic bound. This belongs to the data structures and algorithms subfield of computer science, as a refinement of the binary tree for the ordered-dictionary problem.
A binary search tree is a binary tree obeying the ordering invariant that, for every node, all keys in its left subtree are lesser (or lesser-or-equal, to admit duplicates) and all keys in its right …