Can we define a new data type in a GDB session

Yes, here is how to make this work:

// sample.h
struct sample {
  int i;
  struct sample *less;
  struct sample *more;
};

// main.c
#include <stdio.h>
#include <assert.h>
#include "sample.h"
int main()
{
  struct sample sm;
  sm.i = 42;
  sm.less = sm.more = &sm;

  printf("&sm = %p\n", &sm);
  assert(sm.i == 0);  // will fail
}

gcc main.c   # Note: no '-g' flag

gdb -q ./a.out
(gdb) run
&sm = 0x7fffffffd6b0
a.out: main.c:11: main: Assertion `sm.i == 0' failed.

Program received signal SIGABRT, Aborted.
0x00007ffff7a8da75 in raise ()
(gdb) fr 3
#3  0x00000000004005cc in main ()

No local variables, no type struct sample:

(gdb) p sm
No symbol "sm" in current context.
(gdb) p (struct sample *)0x7fffffffd6b0
No struct type named sample.

So we get to work:

// sample.c
#include "sample.h"
struct sample foo;

gcc -g -c sample.c

(gdb) add-symbol-file sample.o 0
add symbol table from file "sample.o" at
    .text_addr = 0x0

(gdb) p (struct sample *)0x7fffffffd6b0
$1 = (struct sample *) 0x7fffffffd6b0
(gdb) p *$1
$2 = {i = 42, less = 0x7fffffffd6b0, more = 0x7fffffffd6b0}

Voilà!