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; 
}

Subscribe to Post, Code and Quiet Time.

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
jamie@example.com
Subscribe