Concepts

Binary Search Tree

Data Structure

Citation Formats

General Reference

Computing Atlas. "Binary Search Tree." Accessed August 30, 2026. https://computing.interactiveatlas.org/concepts/binary-search-tree.

APA Style

Computing Atlas. (n.d.). Binary Search Tree. Retrieved August 30, 2026, from https://computing.interactiveatlas.org/concepts/binary-search-tree

BibTeX

@misc{computingatlas-binary-search-tree,
  author = {Computing Atlas},
  title = {Binary Search Tree},
  year = {2026},
  url = {https://computing.interactiveatlas.org/concepts/binary-search-tree},
  note = {Accessed August 30, 2026}
}

A node-based tree data structure in which each node's left subtree holds only lesser values and its right subtree only greater ones, giving search, insertion and deletion roughly proportional to the tree's height. The structure was discovered independently by several researchers around 1960, including P.F. Windley, Andrew Donald Booth, Andrew Colin and Thomas N. Hibbard; it is formally attributed to Conway Berners-Lee and David Wheeler, who used it for storing labeled data on magnetic tape in 1960, while Hibbard's own variant became especially influential in practice. A genuine case of simultaneous discovery rather than a single inventor, and a different entity from this atlas's existing Binary Search algorithm despite the shared name.

Facts

Disputed

Origin Year

1960 1

Several researchers (Windley, Booth, Colin, Hibbard) described the structure independently around 1960; formal attribution to Berners-Lee and Wheeler names one specific 1960 application (magnetic tape storage) rather than settling a single inventor for the underlying idea.

Core Principle

Every node orders its two subtrees, lesser values left and greater values right, so a search can discard half the remaining tree at each step, the same principle behind binary search on a sorted array. 1

Cross-Tradition Connections