Find the minimum larger node in binary search tree for a giving node.

Question:
Find the minimum larger node in binary search tree for a giving node.
Answer:
struct BSTreeNode {
BSTreeNode* pLeft;
BSTreeNode* pRight;
BSTreeNode* pParent;
int value;
};
BSTreeNode* findMinLarge(BSTreeNode* node) {
if (!node)
return 0;
if (Node* result = node->pRight) {
while (result && result->pLeft) {
result = result->pLeft;
}
return result;
}
if (node->pParent == 0) {
return 0;
}
if (node->pParent->pLeft == node)
return node->pParent;
BSTreeNode* parent = node->pParent;
BSTreeNode* pparent = parent->pParent;
while (1) {
if (pparent && pparent->pLeft == parent) {
return pparent;
}
if (!pparent)
break;
parent = pparent;
pparent = parent->pParent;
}
return 0;
}

Comments

Popular posts from this blog

How to fix error : no module named sendgrid when try to use sendgrid python lib in PHP.

react-native run-android : sun.security.provider.cert path.SunCertPathBuilderException : unable to find valid certification path to req uested target

react-native run-android : do not build/update modified code(App.js)