- If no right child, then parent should be the next in-order value node if it's parent's left node.
- If no right child, then parent should NOT be the next in-order value node if it's parent's right node.
Here is the code:
node_type_t *_find_next(node_type_t *nodep, int *count)
{
static node_type_t *srcnd = NULL;
static int scan_down = 1;
if (nodep == NULL) {
printf("find_next(node='%d'): got error\n",
(srcnd != NULL ? srcnd->info : -1));
return NULL;
}
if (*count == 0) {
srcnd = nodep;
*count += 1;
}
if (nodep->info info) {
if (nodep->parent != NULL)
return(_find_next(nodep->parent, count));
else {
printf("Can't find next node of '%d'\n", srcnd->info);
return NULL;
}
} else if (nodep->info > srcnd->info) {
if (!scan_down)
return nodep;
if (nodep->left != NULL)
_find_next(nodep->left, count);
else return nodep;
} else { // nodep->info == srcnd->info
if (nodep->right != NULL) {
scan_down = 1;
_find_next(nodep->right, count);
} else {
scan_down = 0;
_find_next(nodep->parent, count);
}
}
}
node_type_t *find_next(node_type_t *nodep)
{
int count = 0;
return (_find_next(nodep, &count));
}
As the matter of fact, Arista Network interview expected me to answer different way based on his algorithms which has much worse performance. I felt that interviewer didn't know the idea of recursive approach.