Te paso una pila básica codificada en C. Espero que te sirva.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
 
typedef struct tpila {
    int dato;
    struct tpila *siguiente;
} pila;
 
pila* pila_new() {
    return NULL;
}
 
bool pila_push(pila **top, int dato) {
    bool retValue = false;
    pila *nodo = malloc(sizeof(pila));
 
    if(!nodo)
        goto final_pila_push;
 
    nodo->dato = dato;
    nodo->siguiente = *top;
    *top = nodo;
 
    retValue = true;
final_pila_push:
    return retValue;
}
 
bool pila_pop(pila **top, int *dato) {
    bool retValue = false;
    pila *nodo = *top;
 
    if(!nodo)
        goto final_pila_pop;
 
    *dato = nodo->dato;
    *top = nodo->siguiente;
 
    free(nodo);
 
    retValue = true;
final_pila_pop:
    return retValue;
}
 
bool pila_top(pila ** const top, int *dato) {
    bool retValue = false;
 
    if(!*top)
        goto final_pila_top;
 
    *dato = (*top)->dato;
 
    retValue = true;
final_pila_top:
    return retValue;
}
 
void pila_free(pila **top) {
    pila *nodo;
 
    while(*top) {
        nodo = *top;
        *top = nodo->siguiente;
        free(nodo);
    }
}
 
int main() {
    int n;
    pila *p = pila_new();
 
    setlocale(LC_ALL, "spanish");
 
    pila_push(&p, 5);
    pila_push(&p, 2);
    pila_push(&p, 3);
 
    pila_top(&p, &n);
    printf("En la pila está el valor %d\n", n);
 
    pila_pop(&p, &n);
    printf("Se saca de la pila el valor %d\n", n);
 
    pila_pop(&p, &n);
    printf("Se saca de la pila el valor %d\n", n);
 
    pila_free(&p);
}

No estoy del todo seguro pero si se trata de punteros creo que no es necesario pasarlo por referencia. Esto es porque un puntero contiene una dirección de memoria, no un dato como tal (variable u objeto).
Si se trata de una variable/objeto hay que pasarlo por referencia porque sino se crea una copia al pasarlo por valor y lo que modificamos es la copia, no el original. Pero al tratarse de punteros, estamos pasando una dirección de memoria, entonces aunque se cree una copia del parámetro y se trabaje sobre la copia, la copia es una dirección de memoria (la misma que el puntero original y por esto es que también funciona). Si se quiere reservar memoria sobre un puntero entonces sí hay que pasarlo por referencia.

Por otra parte el tema de que para un BST se pase por referencia es porque así evitas que la función copie todo el BST por valor. Muchas veces se aprovecha el paso por referencia cuando se trabaja con objetos de gran tamaño para evitar que se haga una copia y así ahorrar espacio en memoria. Por eso hay funciones que reciben objetos constantes por referencia, que parece una tontería ya que al ser constante no se puede modificar pero se hace sólo para evitar que la función ocupe el doble de memoria haciendo una copia del objeto. Para objetos pequeños o variables sencillas es indiferente ya que el gasto de memoria es pequeño pero también podría hacerse. Lo más común es hacer esto con objetos que son muy grandes o que son dinámicos por si llegan a ser muy grandes.

typedef struct tnodo *pnodo; 
// ...
void push_stack(tpila &pila, pnodo nuevo)
 

El parámetro que mandas es <pnodo> y <pnodo> es un puntero a <tnodo>. Al final, lo que estás mandando es un puntero, pero en vez de ser un puntero a una variable es un puntero a un objeto pero no deja de ser un puntero.

Si tus funciones en vez de recibir un <pnodo> (puntero a <tnodo>)  como parámetro, recibiesen un <tnodo> entonces si tendrías que pasarlo por referencia si lo quieres modificar.