Creo que la definición del árbol tiene un error, debería tener una ‘,’ antes del 6. Si los hijos de 6 y de 2 están separados por comas ¿por qué no lo están los hijos de 4?. Si 2 no tuviera hijos quedaría 4( 2 6( 5, 7)) que no parece correcto. Supongo que la ausencia de esa coma es un error del enunciado. ¿Estoy en lo cierto? Si realmente no hay coma ahí, tampoco pasa nada, se puede parsear en cualquier caso.

He convertido la definición en forma de cadena a una representación recursiva, más acorde con un árbol. La función para hacer la conversión es:

def parse(data):
  retval = []
  val = ''
  i = 0
 
  while i < len(data):
    v = data[i]
    i += 1
 
    if v in ',() ':
      if val: retval.append((val,))
      val = ''
    else: val += v
 
    if v == '(':
      n, children = parse(data[i:])
      i += n
      retval[-1] = (retval[-1][0], children)
 
    if v == ')': break
 
  return i, retval

Siendo data la cadena del enunciado, esta función (quitando los espacios) devuelve:

>>> print parse(data.replace(' ',''))
(16, [('4', [('2', [('1',), ('3',)]), ('6', [('5',), ('7',)])])])

La función parse() devuelve una dupla con el nº de caracteres realmente parseados y el árbol en si. Cada nodo del árbol es una dupla, siendo el primer elemento el valor del nodo y el segundo una lista con sus hijos.

La función para “pintar” un árbol con este formato es:

def draw(A, conn=[]):
  for i,v in enumerate(A):
    lin = ''
    c = '+'
 
    if len(A) == i+1: c = '`'
    for r in conn:
      if r: lin += '| '
      else: lin += '  '
 
    print '%s%s-%s' % (lin, c, v[0])
    if len(v) > 1:
      draw(v[1], conn + [len(A) != i+1])

que pinta esto:

`-4
  +-2
  | +-1
  | `-3
  `-6
    +-5
    `-7

que no es tan bonito como el ejemplo del enunciado, pero refleja perfectamente la estructura del árbol.