Lowest Common Ancestor S30000

Donat un BST a (no buit, que conté nombres enters com a elements, i tots són diferents) i dos nombres enters p i q tal que:

• són elements d’a

• són diferents

volem trobar el Lowest Common Ancestor (LCA, en català seria el “node més baix comú”) de p i q dins l’arbre a.

L’LCA de p i q, respecte d’a, es defineix com el node més baix de l’arbre a que té tant p com q com a descendents. Cal tenir en compte que un node es pot considerar descendent de sí mateix, és a dir, si un dels nodes p o q és un avantpassat de l’altre, aleshores aquest node avantpassat seria el LCA.

Escriviu dues funcions que calculin l’LCA de p i q, respecte d’a. Una d’elles (lca_recur(a,p,q)) ho farà recursivament i l’altre (lca_iter(a,p,q)) iterativament.

Paràmetres i retorn de la funció demanada

Els paràmetres de les dues funcions són: un arbre a que és un BST no buit amb nombres enters, tots diferents, com a elements, dos enters diferents p i q, que són elements del BST a.

El retorn de totes dues funcions és un nombre enter.

Entrada

L’entrada al programa serà: un nombre n i una llista d’n nombres enters diferents amb els que construirem el BST.

Després venen dos nombres enters diferents (tots dos han d’estar en la llista amb la que acabem de construir el BST).

Vegeu els exemples del joc de proves públic.

Sortida

La sortida han de ser dos nombres enters, separats per un espai. Tots dos haurien de ser iguals. Un d’ells és l’LCA de l’entrada calculat recursivament, i l’altre és l’LCA de l’entrada calculat iterativament (vegeu el programa principal a code.py).

Vegeu els exemples del joc de proves públic.

Observacions

Heu de baixar-vos el fitxer code.py (icona de la serp). Aquest fitxer és un programa amb tot el que cal per executar els jocs de prova públics. Només falta, clar, les funcions que us demana l’enunciat. Aquest fitxer l’heu de completar amb el codi que falta, i això, tot, és el que heu d’enviar al Jutge com a solució.

Dins el fitxer code.py teniu la classe BST que hem treballat a les classes de l’assignatura. Ha estat modificada per fer més senzilla la solució del problema (vegeu els comentaris a code.py). No caldrà que la vostra solució faci cap import ni res. Tot el codi que us cal el teniu dins de code.py.

L’eficiència i la qualitat de la solució es tindran en compte a la correcció manual.