Podczas wykonywania procedury należy rozważyć trzy przypadki: w przypadku, gdy usuwany węzeł nie ma synów (jest liściem) usunięcie przebiega bez reorganizacji drzewa – wskaźnik do węzła w jego ojcu zastępowany jest wskaźnikiem do węzła pustego w przypadku, gdy usuwany węzeł ma jednego syna to dany węzeł usuwamy a jego syna podstawiamy w miejsce usuniętego węzła w przypadku, gdy usuwany węzeł ma dwóch synów to po jego usunięciu wstawiamy w jego miejsce węzeł, który jest jego następnikiem (który nie ma lewego syna).
define BST_TREE_DELETE (Tree, DeleteNode): if (DeleteNode->Left==NULL) or (DeleteNode->Right==NULL) y=DeleteNode else y=BST_FIND_SUCCESSOR(DeleteNode) if (y->Left != NULL) x=y->Left else x=y->Right if (x!=NULL) x->parent = y->parent if (y->parent == NULL) Tree->root = x else if (y == y->parent->Left) y->parent->Left = x else y->parent->Right = x if (y != DeleteNode) DeleteNode->Key = y->Key // Jeśli y ma inne pola, to je także należy skopiować return y
Wyważanie drzewa thumb|294x294px|Drzewo niezrównoważone (np. lewe poddrzewo węzła 76 ma wysokość 3, a prawe 0)