Diametrul unui arbore binar
Într-o rețea de calculatoare legată ca un arbore, cât de departe sunt cele mai îndepărtate două aparate? Răspunsul este diametrul arborelui. Vei vedea cum o soluție naivă O(n²) devine O(n) când calculezi înălțimea și diametrul în aceeași parcurgere.
Ce este diametrul
Diametrul este numărul de muchii de pe cel mai lung drum dintre oricare două noduri ale arborelui. Drumul nu trebuie să treacă prin rădăcină și nu trebuie să pornească dintr-o frunză anume.
Scrie funcția diametru(radacina) care returnează numărul de muchii de pe cel mai lung drum dintre două noduri, într-o singură parcurgere (O(n)). Pentru arborele gol, rezultatul este 0.
- Scrie o funcție interioară adancime(nod) care întoarce 0 pentru None și 1 + max(stanga, dreapta) altfel.
- La fiecare nod actualizează cel mai bun diametru cu stanga + dreapta (folosește nonlocal).
- Trebuie să apară: 3, 1, 0, 0, 4.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan