Cita: Sobre estos árboles he visto muchos ejemplos en POO. Pero no sé como hacerlos mediante listas o funciones.
El tl;dr de las clases es definir una serie de funciones sobre un conjuntos de estructuras de datos y que el acceso a esos datos este restringido por la clase.
Dicho esto, básicamente esos ejemplos que haz visto en POO, es usando probablemente listas y funciones de algún modo.
Incluso ya hay una implementación en python de lo que intentas hacer:
http://www.leaseweblabs.com/2013/12/...tk-minimax-ai/
Spoiler: No requieres un árbol.