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

Validarea unui BST compară doar cu copiii direcți și acceptă arbori greșiți

Pe scurt

Într-un arbore binar de căutare, toate valorile din subarborele stâng trebuie să fie mai mici decât nodul, nu doar copilul stâng. Transmite în recursivitate un interval permis (minim, maxim) și verifică fiecare nod față de el.

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

Ce înseamnă

Definiția unui BST: pentru fiecare nod, toate valorile din subarborele stâng sunt mai mici, iar toate cele din subarborele drept mai mari. Verificarea „copilul stâng < nod < copilul drept”, aplicată recursiv, pare echivalentă, dar nu e: în arborele cu rădăcina 10, copilul stâng 5 și copilul drept al lui 5 egal cu 12, fiecare pereche părinte-copil e corectă, însă 12 se află în stânga lui 10.

Codul returnează True pentru un arbore invalid, iar căutările în el ar rata valori. În „Repară tu” testul cu assert arată rezultatul.

Reparația: fiecare nod moștenește un interval permis. Rădăcina are (-inf, inf); când cobori la stânga, maximul devine valoarea nodului; la dreapta, minimul devine valoarea nodului. Alternativ, parcurgerea în inordine a unui BST trebuie să dea valori strict crescătoare.

De ce apare: cauzele frecvente

1Verificare locală părinte-copil

Greșit
PYTHON
def e_bst(nod):
    if nod is None:
        return True
    if nod.st and nod.st.val >= nod.val:
        return False
    if nod.dr and nod.dr.val <= nod.val:
        return False
    return e_bst(nod.st) and e_bst(nod.dr)
Corect
PYTHON
def e_bst(nod, mic=float('-inf'), mare=float('inf')):
    if nod is None:
        return True
    if not mic < nod.val < mare:
        return False
    return e_bst(nod.st, mic, nod.val) and e_bst(nod.dr, nod.val, mare)

Intervalul strâns la fiecare coborâre conține toate constrângerile strămoșilor, nu doar a părintelui.

2Inordine fără comparația cu valoarea anterioară

Greșit
PYTHON
valori = inordine(radacina)
return valori == sorted(valori)
Corect
PYTHON
valori = inordine(radacina)
return all(a < b for a, b in zip(valori, valori[1:]))

sorted acceptă și valori egale. Dacă BST-ul cere valori distincte, verifică ordinea strict crescătoare.

Repară tu

Repară eroarea, direct în pagină

Funcția e_bst(nod) verifică dacă un arbore e arbore binar de căutare, dar acceptă arborele în care 12 apare în stânga lui 10. Testul cu assert pică. Repar-o ca testele să treacă și să afișeze False și True.

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

def e_bst(nod):
    if nod is None:
        return True
    if nod.st and nod.st.val >= nod.val:
        return False
    if nod.dr and nod.dr.val <= nod.val:
        return False
    return e_bst(nod.st) and e_bst(nod.dr)

stricat = Nod(10, Nod(5, Nod(2), Nod(12)), Nod(15))
bun = Nod(10, Nod(5, Nod(2), Nod(7)), Nod(15, None, Nod(20)))
for arbore, corect in [(stricat, False), (bun, True)]:
    rez = e_bst(arbore)
    assert rez == corect, f'validare gresita: {rez}'
    print(rez)
După reparație, programul afișează
False
True
Indiciu

Transmite fiecărui apel limitele permise (mic, mare) și strânge-le când cobori la stânga sau la dreapta.

Cum o eviți pe viitor

Când verifici o proprietate de arbore, întreabă-te dacă depinde doar de părinte sau de toți strămoșii. Pentru BST, folosește intervalul (min, max) sau inordinea. Testează mereu cu arborele-capcană: un nod adânc care respectă părintele, dar nu bunicul. Hotărăște și ce faci cu valorile egale (de obicei nu sunt permise).

Întrebări frecvente

De ce float('-inf') și float('inf')?

Rădăcina nu are nicio restricție, iar infinitul e mai mic, respectiv mai mare decât orice număr. Așa nu ai nevoie de cazuri speciale pentru None.

Ce complexitate are verificarea cu interval?

O(n) timp, fiecare nod e vizitat o dată, și O(h) memorie pentru recursivitate, unde h e înălțimea arborelui.

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.