BST property
The rule that keeps a binary search tree searchable: left subtree keys are smaller than the node, right subtree keys are larger.
In more detail
Every insert and delete must preserve it, and an in-order traversal that comes out sorted confirms it holds. A common policy for duplicates is simply not to insert an equal key twice.
Related terms
- binary search tree — A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
- loop invariant — A statement about a loop's variables that is true before the loop starts and stays true after every iteration.
- in-order traversal — Visiting a binary tree's left subtree, then the node itself, then its right subtree.
Taught in
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers