You probably well know that double* is a pointer to a double element. In the same way, double** is a pointer to a double* element, which is itself a pointer. Again, double*** is a pointer to a double** element, and so on.

When you instanciate an array to a type T, you usually do new T [size];. For example, for an array of double, you write new double[size];. If your type T is a pointer itself, it's exactly the same : you write new double*[size];, and you get an array of pointers.

In your case, BTreeNode* is a pointer to BTreeNode, and BTreeNode** is a pointer to BTreeNode* which is a pointer to BTreeNode. When you instanciate it by doing new BTreeNode*[size]; you get an array of pointers to BTreeNode elements.

But actually, at this step you don't have a 2D array, because the pointers in your freshly allocated array are NOT allocated. The usual way to do that is the following example :

int num_rows = 10;
int num_cols = 20;
BTreeNode** C = new BTreeNode*[num_rows];
for(int i = 0; i < num_rows; i++)
{
  // Then, the type of C[i] is BTreeNode*
  // It's a pointer to an element of type BTreeNode
  // This pointer not allocated yet, you have now to allocate it
  C[i] = new BTreeNode [num_cols];
}

Don't forget to delete your memory after usage. The usual way to do it is the following :

for(int i = 0; i < num_rows; i++)
  delete [] C[i];
delete [] C;

If the code you reference in your question was given to you by your professor as an example of the use of pointer arrays of pointers to pointers, I'm not sure how much good that class will actually do. I suspect it was either provided as a debugging exercise or it may have been your attempt at a solution. Regardless, if you simply compile with Warnings enabled, you will find a number of problems that need attention before you advance to debugging your code.

Regarding the code you reference, while you are free to use a global text buffer, you are far better served by not using a global buffer and passing a pointer to your data as required. There are some instances, various callback functions, etc. that require global data, but as a rule of thumb, those are the exception and not the rule.

Your question basically boils down to "How do I properly use an array of pointers and double-pointers (pointer-to-pointer-to-type) variables. There is no way the topic can be completely covered in one answer because there are far too many situations and contexts where one or the other can be (or should be) used and why. However, a few examples will hopefully help you understand the basic differences.

Starting with the array of pointers to type (e.g. char *array[]). It is generally seen in that form as a function argument. When declared as a variable it is followed with an initialization. e.g.:

char *array[] = { "The quick",
                  "brown fox",
                  "jumps over",
                  "the lazy dog." };

char *array[]; by itself as a variable declaration is invalid due to the missing array size between [..]. When used globally, as in your example, the compiler will accept the declaration, but will warn the declaration is assumed to have one element.

The elements of array declared above are pointers to type char. Specifically, the elements are pointers to the string-literals created by the declaration. Each of the strings can be accessed by the associated pointer in array as array[0], ... array[3].

A pointer to pointer to type (double-pointer), is exactly what its name implies. It is a pointer, that holds a pointer as its value. In basic terms, it is a pointer that points to another pointer. It can be used to access the members of the array above by assigning the address of array like:

char **p = array;

Where p[1] or *(p + 1) points to "brown fox", etc.

Alternatively, a number of pointer to pointer to type can be dynamically allocated and used to create an array of pointers to type, that can then be allocated and reallocated to handle access or storage of an unknown number of elements. For example, a brief example to read an unknown number of lines from stdin, you might see:

#define MAXL 128
#define MAXC 512
...
char **lines = NULL;
char buf[MAXC] = {0};
lines = malloc (MAXL * sizeof *lines);
size_t index = 0;
...
while (fgets (buf, MAXC, stdin)) {
    lines[index++] = strdup (buf);
    if (index == MAXL)
        /* reallocate lines */
}

Above you have lines, a pointer-to-pointer-to-char, initially NULL, that is use to allocate MAXL (128) pointers-to-char. Lines are then read from stdin into buf, after each successful read, memory is allocated to hold the contents of buf and the resulting start address for each block of memory is assigned to each pointer line[index] where index is 0-127, and upon increment of index to 128, index is reallocated to provide additional pointers and the read continues.

What makes the topic larger than can be handled in any one answer is that an array of pointers or pointer to pointer to type can be to any type. (int, struct, or as a member of a struct to different type, or function, etc...) They can be used linked-lists, in the return of directory listings (e.g opendir), or in any additional number of ways. They can be statically initialized, dynamically allocated, passed as function parameters, etc... There are just far too many different contexts to cover them all. But in all instances, they will follow the general rules seen here and in the other answer here and in 1,000's more answers here on StackOverflow.

I'll end with a short example you can use to look at the different basic uses of the array and double-pointer. I have provided additional comments in the source. This just provides a handful of different basic uses and of static declaration and dynamic allocation:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main (void) {

    /* array is a static array of 4 pointers to char, initialized to the 
       4 string-literals that a part of the declaration */
    char *array[] = { "The quick",
                    "brown fox",
                    "jumps over",
                    "the lazy dog." };
    /* p is a pointer-to-pointer-to-char assigned the address of array */
    char **p = array;
    /* lines is a pointer-to-pointer-to-char initialized to NULL, used
       below to allocate 8 pointers and storage to hold 2 copes of array */
    char **lines = NULL;
    size_t narray = sizeof array/sizeof *array;
    size_t i;

    printf ("\nprinting each string-literal at the address stored by\n"
            "each pointer in the array of ponters named 'array':\n\n");
    for (i = 0; i < narray; i++)
        printf (" %s\n", array[i]);

    printf ("\nprinting each string using a pointer to pointer to char 'p':\n\n");
    for (i = 0; i < narray; i++, p++)
        printf (" %s\n", *p);

    p = array;
    printf ("\nprinting each line using a pointer to pointer"
            " to char 'p' with array notation:\n\n");
    for (i = 0; i < narray; i++)
        printf (" %s\n", p[i]);

    /* allocate 8 pointers to char */
    lines = malloc (2 * narray * sizeof *lines);

    /* allocate memory and copy 1st 4-strings to lines (long way) */
    for (i = 0; i < narray; i++) {
        size_t len = strlen (array[i]);
        lines[i] = malloc (len * sizeof **lines + 1);
        strncpy (lines[i], array[i], len);
        lines[i][len] = 0;
    }

    /* allocate memory and copy 1st 4-strings to lines 
       (using strdup - short way) */
    // for (i = 0; i < narray; i++)
    //     lines[i] = strdup (array[i]);

    /* allocate memory and copy again as last 4-strings in lines */
    p = array;
    for (i = 0; i < narray; i++, p++)
        lines[i+4] = strdup (*p);

    p = lines; /* p now points to lines instead of array */
    printf ("\nprinting each allocated line in 'lines' using pointer 'p':\n\n");
    for (i = 0; i < 2 * narray; i++)
        printf (" %s\n", p[i]);

    /* free allocated memory */
    for (i = 0; i < 2 * narray; i++)
        free (lines[i]);
    free (lines);

    return 0;
}

Let me know if you have any questions. It a large topic with a relatively small set of rules that can be applied in whole lot of different ways and in different contexts.

For starters this assignment

q = A;

is incorrect because the left operand (having the type int ( ** )[3]) and the right operand (having the type int ( * )[3] after the implicit conversion of the array designator to a pointer to its first element) have different types and there is no implicit conversion between the types.

The compiler can issue an error like this

error: assignment to ‘int (**)[3]’ from incompatible pointer type ‘int (*)[3]’

You could write instead

q = &p;

In this call of printf

printf("*p is : %d\n", *p);

there is used an incorrect argument. The type of the expression *p is int[3]. So in fact you are trying to output a pointer (due to implicit conversion of the array designator to a pointer to its first element) using the conversion specifier %d that is designed to output integers.

Here is a demonstrative program.

#include <stdio.h>

int main(void) 
{
    int A[2][3] = {{1100, 1200, 1300}, {1400, 1500, 1600}};
    int (*p)[3], (**q)[3];
    p = A;
    q = &p;
    
    printf( "A  is : %p\n", ( void * )A );
    printf( "*p is : %p\n", ( void * )*p );
    printf( "*q is : %p\n", ( void * )*q);
    
    return 0;
}

Its output might look like

A  is : 0x7ffdb1c214e0
*p is : 0x7ffdb1c214e0
*q is : 0x7ffdb1c214e0

That is the first call of printf output the initial address of the first element A[0] (of the type int[3]) of the two-dimensional array.

The second call of printf outputs the address of the first element of the first "row" of the two-dimensional array that is &A[0][0].

The third call of printf outputs the value stored in the pointer p that is the address of the first "row" of the two-dimensional array A.

If you want to output the first elements of the array A using the pointers then the program can look the following way.

#include <stdio.h>

int main(void) 
{
    int A[2][3] = {{1100, 1200, 1300}, {1400, 1500, 1600}};
    int (*p)[3], (**q)[3];
    p = A;
    q = &p;
    
    printf( "**p  is : %d\n", **p );
    printf( "***q is : %d\n", ***q);
    
    return 0;
}

Now the program output is

**p  is : 1100
***q is : 1100

The pointer ptr is not initialized and has an indeterminate value.

int **ptr;

So dereferencing it results in undefined behavior.

*ptr = arr;

You need an intermediate pointer. For example

int *p;
int **ptr = &p;

*ptr = arr;

Or you could allocate the intermediate pointer dynamically like

int **ptr = malloc( sizeof( int * ) );
*ptr = arr;

//...
free( ptr );

Here are two demonstrative programs.

#include <stdio.h>

int main( void )
{
    int arr[3] = {1,2,3};
    int *p;

    int **ptr = &p;

    *ptr = arr;

    printf("%d\n", **ptr);

    return 0;
}

and

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
    int arr[3] = {1,2,3};

    int **ptr = malloc( sizeof( int * ) );

    *ptr = arr;

    printf("%d\n", **ptr);

    free( ptr );

    return 0;
}

The both programs have the output

1

If you need a pointer to the whole array then its declaration can look as it is shown in the demonstrative program below.

#include <stdio.h>

int main( void )
{
    enum { N = 3 };
    int arr[N] = { 1, 2, 3 };

    int ( *ptr )[N] = &arr;

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", ( *ptr )[i] );
    }

    putchar( '\n' );

    return 0;
}

The program output is

1 2 3 

Let’s start with:

int arr[][4]={{1,2,3,4},
              {5,6,7,8},
              {9,10,11,12},
             };

print(arr,3,4);

In print(arr,3,4);, arr is an array. Specifically, it is an array of 3 elements, each of which is an array of 4 elements, each of which is an int. Thus, arr is an array of 3 arrays of 4 int. You have probably heard or read that arrays “decay” to pointers. This is a colloquial term. The actual rule, which you can find in clause 6.3.2.1, paragraph 3, of the C 2011 standard, is:

Except when it is the operand of the sizeof operator, the _Alignof operator, or the unary & operator, or is a string literal used to initialize an array, an expression that has type “array of type” is converted to an expression with type “pointer to type” that points to the initial element of the array object and is not an lvalue.

Here is how this rule applies to arr in print(arr,3,4);:

• arr is an identifier, meaning it is the name of some object. As such, it designates its object. That object is an array of 3 arrays of 4 int.
• This array is not the operand of sizeof or Alignof or &, and it is not a string literal. So, following the rule, it is converted from an array of 3 arrays of 4 int to a pointer to the first array of 4 int.

What happens next? Nothing. The expression we have is a pointer to an array of 4 int. There is no rule that says a pointer to an array is converted to a pointer to a pointer. We have a pointer to an array, but that array is not used in an expression yet, not in the simple expression arr. So it is not converted.

This means what you are passing to print is a pointer to an array of 4 int. But your declaration for print says it takes a pointer to a pointer to an int. Those are different things, and they are incompatible, so the compiler warns you.

(To see they are incompatible, consider the difference to a pointer to an array of 4 int and a pointer to a pointer to int. The memory at a pointer to an array of 4 int contains 4 int values. The memory at a pointer to a pointer to an int contains a pointer. These are very different things.)

Next, consider:

void print (int **A, int m, int n)
…
    printf("%d  ", *((A+(m * 4) + n)));

We know from above that you ought to change int **A to int (*A)[4], which is a pointer to an array of 4 int. You can also change it to int A[][4], because there is a rule in C that such a parameter declaration will be automatically adjusted to be int (*A)[4], as a convenience. However, suppose you keep it as int **A. Then does *((A+(m * 4) + n)) mean?

Since A is a pointer to a pointer to an int, then A+(m * 4) means to add m * 4 to the pointer. (That is strange spacing, by the way. m and 4 are more tightly bound by the higher-precedence multiplication than A and (m * 4) are by the addition, so why do they have looser spacing? A + m*4 would portray the meaning better.) Then A+(m * 4) + n means to add n to that. In total, we have moved m*4+n elements beyond where A points. Since A points to a pointer, we have advanced the pointer by m*4+n pointers. Then *((A+(m * 4) + n))) dereferences that. When you dereference a pointer to a pointer to an int, you get a pointer to an int. So the result of this expression is a pointer. But you wanted an int.

The link you reference talks about a “2D array”. The kinds of arrays it talks about are implemented using pointers to pointers. To create such an array, you create an array of pointers, and then you set each of those pointers to point to the elements of a row. Then a pointer to that array of pointers acts like a 2D array, in that A[i][j] refers to element j of row i. If you had an array like that, you could refer to element n of row m using A[m][n]. Equivalently, you could refer to it with *(*(A+m)+n). What this expression means is:

• Take the pointer A and add m to it. Since A points to a pointer to an int, adding m advances the value of the pointer to point to m pointers further along. That is where we should find the pointer to the elements of row m.
• *(A+m) gets the value of the pointer that A+m points to. This value should be a pointer to the elements of row m, specifically a pointer to the first element (with index 0).
• *(A+m)+n advances the value of the pointer to point n int further along. That is where we should find element n of row m.
• *(*(A+m)+n) gets the value of the int that *(A+m)+n points to.

Now suppose instead you changed print to be print(int A[][4], int m, int n). Then your printf statement should use A[m][n], just as before. Or it could use *(*(A+m)+n), also just as before. But, in this case, the expression is evaluated:

• A is a pointer to an array of 4 int. Adding m to it advances value of the pointer to point m arrays further along.
• *(A+m) gets the object that A+m points to. This object is an entire array. So this is an expression that designates an array. Following the C rule about arrays in expressions, this array is converted to a pointer to its first element. Thus, *(A+m) becomes a pointer to the first element of the array numbered m.
• *(A+m)+n advances the value of the pointer to point n int further along. That is where we should find element n of row m.
• *(*(A+m)+n) gets the value of the int that *(A+m)+n points to.

Thus A[m][n] has the same end result for pointers-to-pointers, for pointers-to-arrays, and for arrays-of-arrays, but the steps it goes through for each are different. C knows the types of each subexpression and processes them differently, to achieve the same result.

Finally, suppose you pass &A[0][0] to print and change its parameter to int *A. Now what is the expression *((A+(m * 4) + n)))? In this case, you are treating the array of 3 arrays of 4 int as one big array of 12 int. Then you calculate where element n of row m is. In this case, A is a pointer to int (not a pointer to a pointer to int). So A+(m * 4) + n is a calculation to where element n of row m ought to be, and *((A+(m * 4) + n))) gets the value of that element.

That is a method you ought to avoid when possible. Generally, you should use C’s built-in methods of addressing array elements and avoid doing your own calculations. Whether it is strictly conforming C code or not may depend on how pedantic you are about interpreting certain passages in the C standard.

When used as a function parameter

char a[]  // compiler interpret it as pointer to char

is equivalent to

char *a

and similarly, in main's signature, char *argv[] is equivalent to char **argv. Note that in both of the cases char *argv[] and char **argv, argv is of type char ** (not an array of pointers!).

The same is not true for the declaration

char **r;
char *a[10];

In this case, r is of type pointer to pointer to char while a is of type array of pointers to char.
The assignment

r = a;   // equivalent to r = &a[0] => r = &*(a + 0) => r = a

is valid because in this expression again array type a will be converted to pointer to its first element and hence of the type char **.

Always remember that arrays and pointers are two different types. The pointers and arrays equivalence means pointer arithmetic and array indexing are equivalent.

Suggested reading:

• But I heard that char a[] was identical to char *a.
• Why are array and pointer declarations interchangeable as function formal parameters?