Pseudocod pentru constructie:
== code(cpp) |

Nod-kD construiesteArbore(puncte, directie)
   daca puncte e vida returneaza null
   altfel daca puncte contine un singur punct returneaza Nod-kD(puncte[0])
   altfel
      x = gasesteMediana(puncte, directie)
      // aceasta functie poate fi implementata folosind selectie randomizata
     stanga = puncte cu directie <= x;
     dreapta = puncte cu directie > x;
     t = Nod-kD(x)
     t.stanga = construiesteArbore(stanga, (directie + 1) % 2);
     t.dreapta = construiesteArbore(dreapta, (directie + 1) % 2);
     returneza t

==