s = "A(BB(CC))"
#      012345678


def build_tree(s, root = {"children": [], "l": 0}, i = 0, j = 0):
  if i == len(s):
    return (root, i)

  cs = root["children"]

  if s[i] == ")":
    if cs and isinstance(cs[-1], list):
      cs[-1][1] = i - 1
      cs[-1][3] = j - 1
    root["r"] = root["l"] + 2 * (j - root["l"]) - 1
    return (root, i + 1)

  if s[i] == "(":
    if cs and isinstance(cs[-1], list):
      cs[-1][1] = i - 1
      cs[-1][3] = j - 1
    child, next_i, = build_tree(s, {"children": [], "l": j}, i+1, j)
    root["r"] = child["r"]
    root["children"].append(child)
    return build_tree(s, root, next_i, root["r"] + 1)

  if not cs or not isinstance(cs[-1], list):
    root["children"].append([i, None, j, None])

  root["r"] = j
  return build_tree(s, root, i + 1, j + 1)


def query(s, root, l, r):
  out = ""
  for child in root["children"]:
    if isinstance(child, list):
      # leaf starts at or after l
      if l <= child[2] <= r:
        out += s[child[0]:child[1] + 1 - max(0, child[3] - r)]
      # leaf starts before l
      elif child[2] < l <= child[3]:
        out += s[child[0] + l - child[2]:child[1] + 1]
    # parenthetical starts after r
    elif child["l"] > r:
      return out
    # parenthetical ends before l
    elif child["r"] < l:
      continue
    else:
      stored_r = child["l"] + (child["r"] - child["l"]) // 2
      print((l, stored_r, child))
      out += query(s, child, l, min(stored_r, r))
      if r >= stored_r:
        out += query(s, child, max(l, child["l"]), stored_r)
  return out

import json

root, i = build_tree(s)

print(query(s, root, 3, 8))

print(json.dumps(root, indent=2))