Glossary · Phase 7 · Software engineering
Binary search tree
A tree where everything left of a node is smaller and everything right is bigger, so a search goes down one path.
Try it now
Watch node move down the tree: one comparison per level, never visiting the other side.
Learn it properly
Binary search trees and traversals · Insert, search and delete in a sorted tree, walk it four ways, and see why balance and B-trees matter. About 40 minutes.
Other terms from the same lesson
- B-tree: A wide, balanced search tree with many keys per node, used by databases for indexes so lookups need few disk reads.
- balanced tree: A search tree that rearranges itself as keys are added so its height stays small, keeping searches fast.
- in-order traversal: Visiting a tree's left side, then the node, then the right side; for a binary search tree the keys come out sorted.
- post-order traversal: Visiting a node's children before the node itself, which suits totals like a folder's size.
- pre-order traversal: Visiting each node before its children, which suits copying or saving a tree.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.