t = Nod-kD(x)
     t.stanga = construiesteArbore(stanga, (directie + 1) % 2);
     t.dreapta = construiesteArbore(dreapta, (directie + 1) % 2);

     returneza t
==

     returneaza t
==
 
Pentru a nu face de fiecare data selectie randomizata putem pleca de la inceput cu doua liste de puncte, una sortata dupa $x$ si cealalta sortata dupa $y$.
 
Pseudocod pentru cautare pe domeniu ortogonal (Notam cu Q un dreptunghi):
 
== code(cpp) |
puncte cauta(nod-kD, Q)
  daca Q intersectat cu Nod-kD.domeniu e vid atunci returneaza multimea vida
  altfel daca Nod-kD.domeniu e inclus in Q atunci
                returneaza punctele din subarborele cu radacina nod-kD
  altfel returneaza cauta(nod-kD.stanga, Q) reunita cu cauta(nod-kD.dreapta, Q)
==
 
Sa vedem care e complexitatea operatiei **cauta**. Nodurile care sunt total in afara dreptunghiului sau total inauntrul dreptunghiului Q pot cel mult fi de doua ori mai multe decat nodurile care intersecteaza dreptunghiul Q intr-o cautare, pentru ca vizitarea unui nod total in afara dreptunghiului sau unui nod dinauntrul dreptunghiului a pornit de la un nod al carui domeniu intersecteaza dreptunghiul. Pentru analiza ne putem ocupa numai de noduri ale caror domenii intersecteaza dreptunghiul. Pentru a obtine o limita superioara a numarului de zone intersectate putem considera numarul maxim de zone intersectate de o latura a dreptunghiului si sa inmultim acel numar cu patru. Pentru a mai simplifica analiza putem considera nu numarul maxim de zone intersectate de un segment, ci numarul maxim de zone intersectate de o dreapta verticala sau orizontala. Consideram o dreapta verticala, pentru un nod, daca directia de impartire a zonei asociate e verticala atunci dreapta verticala taie sau zona fiului stang sau zona fiului drept, dar nu pe amandoua deodata. Daca dreapta verticala nu intersecteaza zona asociata unui fiu atunci nu va mai intersecta zona nici unui urmas al fiului. In caz contrar intersecteaza ambii fii. Daca coboram la nivelul nepotilor cel mult patru noduri sunt intersectate. In cel mai rau caz intersectam domeniul reprezentat de radacina si putem intersecta cel mult $2^i^$ noduri pana la nivelul $2i$. Deci in total maxim O(sqrt(n)) noduri sunt parcurse la o operatie cauta.