Coding Interview Questions: No. 45 - Closest Node in a Binary Search Tree
Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.
BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
BinaryTreeNode* pClosest = NULL;
int minDistance = 0x7FFFFFFF;
BinaryTreeNode* pNode = pRoot;
while(pNode != NULL)
{
int distance = abs(pNode->m_nValue - value);
if(distance < minDistance)
{
minDistance = distance;
pClosest = pNode;
}
else if(pNode->m_nValue < value)
pNode = pNode->m_pRight;
}
Read full article from Coding Interview Questions: No. 45 - Closest Node in a Binary Search Tree
Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.
BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
BinaryTreeNode* pClosest = NULL;
int minDistance = 0x7FFFFFFF;
BinaryTreeNode* pNode = pRoot;
while(pNode != NULL)
{
int distance = abs(pNode->m_nValue - value);
if(distance < minDistance)
{
minDistance = distance;
pClosest = pNode;
}
if(distance == 0)
break;
if(pNode->m_nValue > value)
pNode = pNode->m_pLeft;else if(pNode->m_nValue < value)
pNode = pNode->m_pRight;
}
return pClosest;
}Read full article from Coding Interview Questions: No. 45 - Closest Node in a Binary Search Tree