Is there a way to implement this binary search tree function?

Question

I am struggling to implement the following function:

Given a binary search tree, return the smallest node, then move the pointer to the next smallest node in the tree. Upon calling the function another time, it should return the next smallest node and so on.

Any help would be greatly appreciated.

Here is my program so far with some helper functions and their definitions:

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data,
   the pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
};
 
struct node *minValue(struct node *node);
 
struct node *inOrderSuccessor(
    struct node *root,
    struct node *n)
{
    if (n->right != NULL)
        return minValue(n->right);
   
    struct node *p = n->parent;
    while (p != NULL && n == p->right) {
        n = p;
        p = p->parent;
    }
    return p;
}
 
/* Given a non-empty binary search tree,
    return the minimum data 
    value found in that tree. Note that
    the entire tree does not need
    to be searched. */
struct node *minValue(struct node *node)
{
    struct node *current = node;
 
    /* loop down to find the leftmost leaf */
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}
 
/* Helper function that allocates a new
    node with the given data and
    NULL left and right pointers. */
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
 
    return (node);
}
 
/* Give a binary search tree and
   a number, inserts a new node with   
    the given number in the correct
    place in the tree. Returns the new
    root pointer which the caller should
    then use (the standard trick to
    avoid using reference parameters). */
struct node *insert(struct node *node,
                    int data)
{
    /* 1. If the tree is empty, return a new,
      single node */
    if (node == NULL)
        return (newNode(data));
    else {
        struct node *temp;
 
        /* 2. Otherwise, recur down the tree */
        if (data <= node->data) {
            temp = insert(node->left, data);
            node->left = temp;
            temp->parent = node;
        } else {
            temp = insert(node->right, data);
            node->right = temp;
            temp->parent = node;
        }
 
        /* return the (unchanged) node pointer */
        return node;
    }
}

Answer 1

Given a binary search tree, return the smallest node, then move the pointer to the next smallest node in the tree. Upon calling the function another time, it should return the next smallest node and so on.

struct node *next_smallest_node(struct node *root, struct node *min)
{
    if (!min)
        return min_node(root);
    
    if (min->right)
        return min_node(min->right);
   
    for (struct node *p = min->parent; p; p = min->parent) {
        // Coming from left: return parent
        if (min != p->right)
            return p;
        
        // Coming from right: stop at root
        if (p == root)
            return NULL;
        
        min = p;
    }
    
    return NULL;
}

min_node() returns the smallest node in a tree:

struct node *min_node(struct node *root)
{
    struct node *min = NULL;
    for (struct node *i = root; i; i = i->left) 
        min = i;
    
    return min;
}

Usage:

int main(void)
{
    struct node *tree = NULL;
    // Fill tree with data ...
    
    struct node *min = NULL;
    while (min = next_smallest_node(tree, min)) {
        printf("Next smallest = %d\n", min->data);
    }
}

---

Update:

• The code in next_smallest_node() now parses the left sub-tree (thanks to @chqrlie).
• There's no need to compute the minimum value prior to calling the function.