Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

Arbres binaris de cerca - Elements comuns P42342

Statement

thehtml

Feu una funció que, donats dos arbres binaris de cerca de naturals, generi els seus elements comuns en ordre creixent.

Digueu quin és el cost asimptòtic de generar tots els elements comuns de dos arbres binaris de cerca utilitzant el vostre algorisme.

Observacions

Descarregueu-vos el fitxer code.py. El programa principal, les estructures de dades, la lectura de l’arbre i l’esquelet de la funció ja se us dónen implementats. No podeu canviar la interfície ni els tipus donats.
El programa principal serveix per provar la funció i llegeix p parells d’arbres binars de cerca en preordre (amb valors −1 pels arbres buits) i escriu, per a cada parell, els seus elements comuns en ordre creixent en una línia.
No podeu utilitzar llistes, ni conjunts ni diccionaris. Sí que podeu utilitzar funcions auxiliars i generadors.

Public test cases

Input

4

5 3 -1 -1 6 -1 -1
6 5 -1 -1 9 -1 -1

5 3 -1 -1 7 6 -1 -1 -1
1 -1 3 -1 5 -1 7 -1 9 -1 -1

5 3 -1 -1 6 -1 -1
-1

666 -1 -1
666 -1 -1

Output

Information