Devi stare attento all'argomento che passi nella chiamata di funzione ricorsiva e in particolar modo alla profondità di ricorsione che questo genera.
Il problema dovrebbe risiedere in una ricorsione "esagerata", passami il termine, all'interno dell'albero... Questo probabilmente ti consente di far in modo che sui test più piccoli non nasca il problema, ma in quelli più grandi con molti nodi e livelli, questo viene alla luce.
Il consiglio che posso darti è di aprire il PDF dell'albero che ci ha fornito il prof a titolo di esempio, e visualizzare i passaggi che si devono fare per esplorarlo tutto, in modo da trovare il più efficiente.
Mi sembra che il limite di ricorsione standard in python sia fissato a 500 (forse sbaglio). E' un limite che può essere esteso, ma questo non credo sia utile ai fini dell'homework.
Cerca un argomento da passare alla funzione ricorsiva che ti permetta di esplorare tutto l'albero ricorrendo il minor numero di volte, o cerca dei modi per "saltare" delle ricorsioni che sai già non hanno motivo di essere effettuate.
