A complete tree where every node has a key more extreme (greater or less) than the key of its parent. Each node has k or fewer children.