Что это

Это Binary tree, но с одним правилом: все уровни дерева заполнены полностью, за возможным исключением нижнего, который может быть заполнен частично, но строго по определённому правилу: слева направо.

Correct nearly completed binary tree

Incorrect nearly completed binary tree: ‘?’ vertexes are missing

Какие у неё есть методы

int getParent(i) {
	return floor((i - 1) / 2)
}

int getLeftChild(i) {
	return 2*i + 1; 
}

int getRightChild(i) {
	return 2*i + 2; 
}

Max and min number of vertices in nearly-completed binary tree

max - $2^{h+1}-1$

min - $2^h$