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

Parcurgerea în inordine returnează doar rădăcina: rezultatele apelurilor recursive sunt ignorate

Pe scurt

Funcția apelează inordine(nod.stanga) și inordine(nod.dreapta), dar nu folosește ce returnează, deci rezultatul conține doar valoarea nodului curent. Combină rezultatele: return inordine(nod.stanga) + [nod.val] + inordine(nod.dreapta).

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

Ce înseamnă

Într-o funcție recursivă care returnează un rezultat, fiecare apel își construiește propria listă. Dacă scrii inordine(nod.stanga) pe o linie separată, lista construită de subarborele stâng e calculată și apoi aruncată, pentru că nimeni nu o salvează.

Simptomul tipic: parcurgerea unui arbore cu multe noduri returnează [5], adică doar rădăcina. Nu apare nicio eroare, pentru că toate apelurile rulează corect, doar că rezultatele lor nu ajung nicăieri.

Ai două variante corecte: fie combini explicit rezultatele (stanga + [val] + dreapta), fie folosești o singură listă comună, transmisă ca parametru sau definită într-o funcție exterioară, la care fiecare apel adaugă cu append. Nu le amesteca: dacă folosești lista comună, apelurile nu mai trebuie să returneze nimic.

De ce apare: cauzele frecvente

1Rezultatul apelurilor recursive nu e folosit

Greșit
PYTHON
inordine(nod.stanga)
rez = [nod.val]
inordine(nod.dreapta)
return rez
Corect
PYTHON
return inordine(nod.stanga) + [nod.val] + inordine(nod.dreapta)

Fiecare apel returnează lista subarborelui lui, iar concatenarea le pune în ordinea stânga, rădăcină, dreapta.

2Varianta cu listă comună

Greșit
PYTHON
def inordine(nod):
    rez = []
    if nod:
        inordine(nod.stanga)
        rez.append(nod.val)
        inordine(nod.dreapta)
    return rez
Corect
PYTHON
def inordine(nod, rez):
    if nod:
        inordine(nod.stanga, rez)
        rez.append(nod.val)
        inordine(nod.dreapta, rez)
    return rez

Toate apelurile adaugă în aceeași listă rez, transmisă mai departe, deci nimic nu se pierde. E și mai eficientă, pentru că nu copiază liste.

Repară tu

Repară eroarea, direct în pagină

Funcția inordine(nod) trebuie să returneze valorile unui arbore binar de căutare în ordine crescătoare. Testul cu assert pică: rezultatul conține doar rădăcina. Repar-o ca să afișeze [1, 3, 5, 8].

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

def inordine(nod):
    if nod is None:
        return []
    inordine(nod.stanga)
    rez = [nod.val]
    inordine(nod.dreapta)
    return rez

radacina = Nod(5, Nod(3, Nod(1)), Nod(8))
rez = inordine(radacina)
assert rez == [1, 3, 5, 8], f'parcurgere incompleta: {rez}'
print(rez)
După reparație, programul afișează
[1, 3, 5, 8]
Indiciu

Combină listele returnate de cele două apeluri recursive cu valoarea nodului curent.

Cum o eviți pe viitor

La orice funcție recursivă, întreabă-te ce faci cu valoarea returnată de fiecare apel recursiv. Dacă apelul stă singur pe o linie, fără return, atribuire sau +, rezultatul lui se pierde, cu excepția cazului în care funcția modifică o structură comună. Testează pe un arbore cu cel puțin trei niveluri și verifică lungimea rezultatului față de numărul de noduri.

Întrebări frecvente

Care variantă e mai bună?

Cea cu listă comună face O(n) operații în total. Cea cu concatenare copiază liste la fiecare nivel, deci poate ajunge la O(n²) pe arbori dezechilibrați, dar e mai scurtă. Pentru arbori mici, amândouă sunt în regulă.

Cum fac preordinea sau postordinea?

Schimbi doar poziția lui [nod.val]: preordine = [val] + stanga + dreapta, postordine = stanga + dreapta + [val].

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.