How would you write this code in C using arrays instead

Question

void storeBSTNodes(Node* root, vector<Node*> &nodes)
{
  if (root == NULL)
    return;

  storeBSTNodes(root->left, nodes);
  nodes.push_back(root);
  storeBSTNodes(root->right, nodes);
}

How would you write this code in C (it's in C++ format currently) using an array? This is what I've got so far, but I'm confused about the part regarding nodes.push_back(root); and root->left, nodes

void storeBSTNodes(Node* root, int arr[])
{
  if (root == NULL)
    return;

  storeBSTNodes(root->left, arr);
  ?
  storeBSTNodes(root->right, arr);
}

Code from: https://www.geeksforgeeks.org/convert-normal-bst-balanced-bst/

Answer 1

The key is realloc.

But you'll soon realize that Node arr[] would have to be changed since you would need to know the existing number of elements in the array, and you would need to return the new number of elements in the array and the updated buffer pointer. Using a vector-like "class" or library would help.

Given the (untested) library below, you could use the following:

void storeBSTNodes(Node* root, Vector* nodes)
{
  if (root == NULL)
    return;

  storeBSTNodes(root->left, nodes);
  Vector_push(nodes, root);             // Ignores failures.
  storeBSTNodes(root->right, nodes);
}

Vector.h:

#ifndef VECTOR_H
#define VECTOR_H

#include <stdlib.h>

// A fixed-size circular buffer.
typedef struct {
   size_t size;
   size_t used;
   void** buf;
} Vector;

// Returns NULL and sets errno on error.
// Free the vector with Vector_delete when done.
Vector* Vector_new(void);

// Returns 0 and sets errno on error.
// Destroy the vector with Vector_destroy when done.
int Vector_init(Vector* v);

// Inverse of Vector_new.
// Only call when the vector is empty.
void Vector_delete(Vector* v);

// Inverse of Vector_init.
// Only call when the vector is empty.
void Vector_destroy(Vector* v);

int Vector_is_empty(Vector* v);

// Appends an element to the vector.
// Returns 0 and sets errno on error.
int Vector_push(Vector* v, void* ele);

// Removes the last element of the vector and returns it.
// Note that this also NULL if empty.
void* Vector_pop(Vector* v);

#endif

Vector.c:

#include <assert.h>
#include <stdlib.h>

#include "Vector.h"

Vector* Vector_new(void) {
   Vector v = malloc(sizeof(Vector));
   if (v == NULL)
      goto Error1;

   if (!Vector_init(v))
      goto Error2;

   return v;

Error2:
   free(v);
Error1:
   return NULL;
}

int Vector_init(Vector* v) {
   v->size = 0;
   v->used = 0;
   v->buf = NULL;
   return 1;
}

void Vector_delete(Vector* v) {
   Vector_destroy(v);
   free(v);
}

void Vector_destroy(Vector* v) {
   assert(v->used == 0);
   free(v->buf);
}

int Vector_is_empty(Vector* v) {
   return v->used == 0;
}

int Vector_push(Vector* v, void* ele) {
   if (v->used == v->size) {
      size_t new_size = v->size;
      new_size = new_size ? new_size * 2 : 4;

      void* new_buf = realloc(v->buf, new_size * sizeof(void*));
      if (new_buf == NULL)
         return 0;

      v->size = new_size;
      v->buf  = new_buf;
   }

   v->buf[ (v->used)++ ] = ele;
   return 1;   
}

void* Vector_pop(Vector* v) {
   if (v->used == 0)
      return NULL;

   return v->buf[ --(v->used) ];
}

Add other "methods" as needed.