Binary search tree
Also called: BST
A binary tree where every value in a node's left subtree is smaller and every value in its right subtree is larger.
Definition
The ordering rule lets you search, insert and delete by walking down one path, which takes O(log n) when the tree is balanced and O(n) when it degenerates into a line. An in-order traversal visits the values in sorted order. Sorted maps like Java's TreeMap use self-balancing variants such as red-black trees.
In practice
To find 7 in a BST rooted at 4, go right (7 > 4), then right again if the next node is 6.
Learn it in context
Lessons that use this term.