...
Eroare Algoritmi și structuri de date · Arbori și heap-uri

Inserarea în BST pierde nodurile noi: rezultatul apelului recursiv nu e atribuit

Pe scurt

Funcția recursivă returnează nodul nou când ajunge la None, dar dacă nu scrii rad.stanga = insereaza(rad.stanga, val), nodul nu e legat de arbore. Atribuie rezultatul la fiecare nivel și la apelul de sus (rad = insereaza(rad, val)).

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Varianta recursivă elegantă a inserării într-un arbore binar de căutare (BST) se bazează pe o regulă: funcția returnează rădăcina subarborelui după inserare. Când ajunge la un loc gol (None), creează nodul și îl returnează; apelul de deasupra trebuie să-l lege: rad.stanga = insereaza(rad.stanga, val).

Dacă scrii doar insereaza(rad.stanga, val), nodul nou e creat și apoi pierdut. Python nu dă eroare. Arborele rămâne cu rădăcina singură sau cu nodurile de la primul nivel.

Aceeași greșeală apare la nivelul de sus: insereaza(rad, 5) cu rad = None returnează nodul nou, dar variabila rad rămâne None. Și la ștergerea din BST se aplică exact același tipar.

De ce apare: cauzele frecvente

1Apelul recursiv nu e atribuit

Greșit
PYTHON
if val < rad.val:
    insereaza(rad.stanga, val)
else:
    insereaza(rad.dreapta, val)
return rad
Corect
PYTHON
if val < rad.val:
    rad.stanga = insereaza(rad.stanga, val)
else:
    rad.dreapta = insereaza(rad.dreapta, val)
return rad

Atribuirea leagă nodul nou de părintele lui. Pentru subarborii existenți, funcția returnează aceeași rădăcină, deci nu se strică nimic.

2Rădăcina nu e actualizată la apel

Greșit
PYTHON
rad = None
for v in valori:
    insereaza(rad, v)
Corect
PYTHON
rad = None
for v in valori:
    rad = insereaza(rad, v)

Primul apel creează rădăcina; fără atribuire, rad rămâne None și fiecare apel creează un arbore nou, pierdut.

3Atribuire la parametru

Greșit
PYTHON
def insereaza(rad, val):
    if rad is None:
        rad = Nod(val)
        return
Corect
PYTHON
def insereaza(rad, val):
    if rad is None:
        return Nod(val)

rad = Nod(val) schimbă doar variabila locală, nu legătura din părinte.

Repară tu

Repară eroarea, direct în pagină

Funcția insereaza(rad, val) adaugă coduri de produs într-un BST, iar inordine le afișează sortate. Testul cu assert pică: în arbore rămâne doar rădăcina. Repară inserarea ca să afișeze [1, 3, 4, 5, 8].

Codul care dă eroarea
PYTHON
class Nod:
    def __init__(self, val):
        self.val = val
        self.stanga = None
        self.dreapta = None

def insereaza(rad, val):
    if rad is None:
        return Nod(val)
    if val < rad.val:
        insereaza(rad.stanga, val)
    else:
        insereaza(rad.dreapta, val)
    return rad

def inordine(rad):
    if rad is None:
        return []
    return inordine(rad.stanga) + [rad.val] + inordine(rad.dreapta)

rad = None
for v in [5, 3, 8, 1, 4]:
    rad = insereaza(rad, v)
rez = inordine(rad)
assert rez == [1, 3, 4, 5, 8], f'arbore gresit: {rez}'
print(rez)
După reparație, programul afișează
[1, 3, 4, 5, 8]
Indiciu

Rezultatul apelurilor recursive trebuie salvat în rad.stanga și rad.dreapta.

Alte forme ale mesajului

  • AttributeError: 'NoneType' object has no attribute 'val'

Cum o eviți pe viitor

Când o funcție recursivă pe arbori „returnează rădăcina subarborelui”, fiecare apel recursiv trebuie să fie în dreapta unei atribuiri. Verifică după construire cu o parcurgere în inordine: pentru un BST corect, rezultatul e lista sortată a tuturor valorilor inserate. Testează cu cel puțin trei niveluri.

Întrebări frecvente

Nu e mai simplu iterativ?

Varianta iterativă coboară până la un copil None și leagă nodul de părinte. E la fel de corectă; recursivă e mai scurtă, dar cere atribuirile.

De ce Python nu modifică arborele prin parametru?

Parametrii sunt nume locale. Poți modifica atributele obiectului primit (rad.stanga = ...), dar dacă atribui parametrului un obiect nou, apelantul nu vede schimbarea.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.