Za zadatak i resenje je vazno kako se formira stablo. Ako je stablo slucajnog rasporeda sa slucajnim vrednostima cvorova i listova onda ne mozes da prebrojis bez da posetis sve cvorove.

Formira se tako sto levo od svakog cvora idu elementi manji od njega a desno veci, balans vec nije bitan, tako da moze i za ne balansirano stablo.

Mozes da upises u svaki cvor tezinu levog i tezinu desnog cvora tako sto ces kad prolazis kroz stablo prilikom dodavanja noda
dodati +1 svakom listu kroz koji prolazis. To mi je prvo palo napamet. Kada pretrazujes stablo dodjes do cvora
gde su svi levi manji a svi desni veci od zadatog broja i onda procitas tezinu datog cvora.

To je odlicno resenje i tada imam minimalni broj provera cvorova pri pretrazi ali mi nije dozvoljeno da menjam strukturu. Cvor mora da sadrzi tacno ono sto mi je zadato. Posto je obicno binarno stablo(nije balansirano) sme da sadrzi samo podatak i pokazivac na levo i desno dete.

Ako nemas podatak o tezini leve i desne grane u cvoru, onda moras proci celu granu da bi izracunao tezinu.

Ako stablo izgleda ovako i ja hocu da nadjem broj cvorova vecih od 14, zasto onda moram da prodjem i kroz 5,1,8? Zasto ne mogu da kad dodjem do prvog manjeg proverim samo desno od njega i onda se vracam gore, ka roditelju?

Možeš i to je jedina optimizacija koju mogu da vidim.

Pa da, ali kako?

resio sam, evo kako ako nekog interesuje.

A sta ako je stablo ovakvo?

Radi i u tom slucaju, on stigne do petice, i ona nije manja od 14 i tada rekurzivno poziva istu funkciju za desnu granu, desna grana je 8, posto 8 takodje nije manje od 14 opet poziva istu funkciju za desnu granu, tu uveca brojac za 1 jer je 15 vece od 14 i poziva za levu granu, ali sada je p = NULL jer leva grana ne postoji i onda se vraca na gore.