Algorytm wyznaczania następnika jest następujący: define BST_FIND_SUCCESSOR(Node): if (Node->right != NULL) return BST_SEARCH_MIN_KEY(Node->right) Node_tmp = Node->parent while (Node_tmp != NULL and Node_tmp->left != Node) Node = Node_tmp Node_tmp = Node_tmp->parent return Node_tmp
Analogicznie przebiega wyszukiwanie poprzednika: define BST_FIND_PREDECESSOR(Node): if (Node->left != NULL) return BST_SEARCH_MAX_KEY(Node->left) Node_tmp = Node->parent while (Node_tmp != NULL and Node_tmp->right != Node) Node = Node_tmp Node_tmp = Node_tmp->parent return Node_tmp Podobnie jak w poprzednim przypadku wyszukiwanie rozpoczynamy od wywołania procedury BST_FIND_PREDECESSOR z adresem węzła, którego poprzednik chcemy znaleźć. Podczas przeszukiwania mogą zaistnieć dwie sytuacje: istnieje lewe poddrzewo danego węzła – wtedy znalezienie jego poprzednika ogranicza się do znalezienia największego klucza w tym poddrzewie nie istnieje lewe poddrzewo danego węzła – wtedy poprzednikiem jest węzeł będący jednocześnie najniższym przodkiem węzła (którego chcemy znaleźć) oraz mającym prawego syna, który także jest przodkiem danego węzła.