Thread: Creating an ordered array from binary search tree

my node structure is

Code:

typedef struct node_ {

    void * key;
    void * data;
    struct node_ * left;
    struct node_ * right;
}node, *pnode;

The aim is to create an array of generic pointers that point to the data on each node of the tree. The pointers must be in order, meaning from smallest to largest.

My idea is to do an in-order traversal

Code:

void * point_data(node *cur)
{  if (cur->left)    
point_data(cur->left);  
return (cur->data); 
 if (cur->right)    
point_data(cur->right); }

my concern with the above is that after returning (cur->data) the program won't check for the right child. If that is the case, how can i solve it?

also, as mentioned above, i want to create an array of said pointers. How can i do that?

my first reaction was

Code:

void * p[telem];    
int i;
    
    for(i=0; i < (telem-1);i++)
    p[i] = point_data(root);

where root is of type node *. With the above i believe i would just get all pointers pointing to the same first element. I'm at a mental block right now :S any help is greatly appreciated.

C does not have a yield operator like Python, so you cannot separate the action from the iteration. Simply put, you just need to do the array assignment in your tree iterator.

To do that, I would supply the pointer to the dynamically allocated array of node pointers, a pointer to the size of that array (in node pointers), the number of node pointers already in the array, and the tree:
For example,

Code:

int node_array_assign(node ***const arrayptr, size_t *const sizeptr, size_t *const usedptr, node *const tree)
{
    int  error;

    if (tree->left) {
        error = node_array_assign(arrayptr, sizeptr, usedptr, tree->left);
        if (error)
            return error;
    }

    if (*usedptr >= *sizeptr) {
        const size_t  size = 16 + (*usedptr * 5) / 4;
        node **temp;

        temp = realloc(*arrayptr, size * sizeof (*temp));
        if (!temp)
            return ENOMEM;

        *arrayptr = temp;
        *sizeptr = size;
    }

    (*arrayptr)[(*usedptr)++] = tree;

    if (tree->right) {
        error = node_array_assign(arrayptr, sizeptr, usedptr, tree->right);
        if (error)
            return error;
    }

    return 0;
}

To make it a bit easier for the programmer, I'd add a wrapper, perhaps

Code:

size_t node_array(node ***const arrayptr, size_t *const sizeptr, node *const tree)
{
    size_t  used;
    int     result;

    if (!arrayptr || !sizeptr) {
        errno = EINVAL;
        return 0;
    }

    if (!*sizeptr)
        *arrayptr = NULL;

    if (!tree) {
        errno = 0;
        return 0;
    }

    result = node_array_assign(arrayptr, sizeptr, &used, tree);

    if (result) {
        errno = result;
        return 0;
    }

    return used;
}

The allocation logic is similar to the POSIX.1-2008 getline() function: you can initialize the value pointed to by sizeptr to zero, and it will dynamically allocate a large enough buffer. Or you can provide a preallocated array, in which case it will only be reallocated if not large enough yet.

It is, however, "three star code", which is not a compliment.. The array is specified as node ** , i.e. as a pointer to pointer (outer pointer being the array, inner pointer to the node). In order for the functions to reallocate the array when necessary, we need a pointer to the array pointer, i.e. node ***.

Eww. It is ugly and hard to read; pretty much an indication that something is wonky with this approach.

I'm sure I'm going to get flamed for this post and the above code, but it is undeserved, I assure you. If you want an array of pointers to a binary search tree nodes, the above is the most straightforward and simple code I can think offhand. (You can simplify it by traversing the tree twice: first to obtain the number of nodes, then allocating the array to that precise size, then to copy the pointer to each node. However, traversing any sufficiently large binary search tree will be limited by memory accesses, so that approach will be basically half as fast as this one, for large enough trees. Not a good tradeoff in my opinion.)

However, your particular case has a feature that makes another solution much better: Your nodes are fixed-size and small, with just a key and a data pointer. So, instead of filling in an array of pointers to tree nodes, you could instead copy the node contents into the array. For example, using

Code:

typedef struct {
    void *key;
    void *data;
} pair_t;

and have the node_array() instead take a pointer to a pair_t pointer. This will only use twice the memory compared to the array of pointers to each node, but it will be independent of the tree, and you won't need to do the extra indirection; thus, it would be significantly faster for larger tree sizes.

In this case, the functions could be for example

Code:

int tree_pairs_copy(pair_t **const listptr, size_t *const sizeptr, size_t *const usedptr, node *const tree);
size_t tree_pairs(pair_t **const listptr, size_t *const sizeptr, node *const tree);

Ah, that looks much more sane to me; this indeed is the way I'd implement this, I think.

There are only minor differences to the node_array_assign() and node_array() functions I showed earlier, so you should be able to write them yourself.

Any questions?