Este un BST valid?
La interviu primești un arbore și întrebarea „este arbore binar de căutare?”. Pare simplu: compari fiecare nod cu copiii lui. Este exact capcana pe care o caută intervievatorul. Soluția corectă transmite limite în jos, prin arbore.
Problema și capcana
Un arbore este BST valid dacă fiecare nod este mai mare decât toate valorile din stânga lui și mai mic decât toate valorile din dreapta lui. Aici considerăm duplicatele nevalide (comparații stricte).
class Nod:
def __init__(self, val, st=None, dr=None):
self.val, self.st, self.dr = val, st, dr
def doar_copiii(nod): Scrie funcția bst_valid(radacina) care returnează True dacă arborele este BST valid (stânga < nod < dreapta, duplicatele sunt nevalide) și False altfel, transmițând limitele (minim, maxim) în jos. Arborele gol este valid.
- Scrie o funcție ajutătoare verifica(nod, minim, maxim).
- Pornește cu verifica(radacina, -math.inf, math.inf); la stânga maximul devine nod.val, la dreapta minimul devine nod.val.
- Trebuie să apară: True, False, False, True, False, True.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan