Binary search tree

Applies to: general

A binary search tree keeps every left descendant smaller and every right descendant larger than a node, so search, insert, and delete each cost O(height). An inorder traversal visits the values in sorted order. Without balancing it can degrade to a O(n) chain.

      5
     / \
    3   8     inorder -> 2 3 4 5 8
   / \
  2   4

See also: binary-search, recursion