Înălțimea și arborii echilibrați
Cât de „adânc” este un arbore? Răspunsul, înălțimea, decide cât de rapide sunt operațiile pe el: un arbore înalt și subțire se comportă ca o listă înlănțuită, unul echilibrat permite căutări în O(log n). Azi calculezi înălțimea recursiv și verifici dacă un arbore e echilibrat, într-o singură parcurgere.
Înălțimea
Înălțimea este numărul de niveluri de la rădăcină până la cea mai adâncă frunză. Convenția din acest curs: arborele gol are înălțimea 0, o frunză singură are înălțimea 1.
from collections import deque
class Nod:
def __init__(self, val, st=None, dr=None):
self.val = val Scrie inaltime(radacina) (numărul de niveluri; arborele gol are 0) și echilibrat(radacina) în O(n): o funcție ajutătoare recursivă returnează înălțimea subarborelui sau -1 dacă nu e echilibrat (diferență de înălțime mai mare decât 1 la vreu…
- inaltime: 1 + max(...) din înălțimile copiilor.
- În funcția ajutătoare: calculează înălțimile copiilor, propagă -1 și verifică abs(st - dr) > 1.
- echilibrat returnează dacă rezultatul ajutătoarei e diferit de -1. Trebuie să apară: 3 True, 4 False, 4 False, 0 True.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan