code: def predict(tree, x, y=[], dist=False):
      node_id = 1
      while 1:
          nodes = tree[node_id]
          if nodes[0][5] == "c":
              if x[nodes[0][1]] <= nodes[0][2]:
                  index, node_id = 0, nodes[0][0]
              else:
                  index, node_id = 1, nodes[1][0]
          else:
              if x[nodes[0][1]] in nodes[0][2]:
                  index, node_id = 0, nodes[0][0]
              elif x[nodes[1][1]] in nodes[1][2]:
                  index, node_id = 1, nodes[1][0]
              else:
                  node_id = str(nodes[0][0]) + "," + str(nodes[1][0])
                  index, nodes = 0, [[0, 0, 0, {k: nodes[0][3].get(k, 0) + nodes[1][3].get(k, 0) for k in
                                                set(nodes[0][3]) | set(nodes[1][3])}]]
          if node_id in tree.keys():
              continue
          if dist:
              suma = sum(nodes[index][3].values())
              return Counter({k: v / float(suma) for k, v in nodes[index][3].iteritems()})
          prediction = max(nodes[index][3], key=nodes[index][3].get)
          if y == []:
              return prediction
          probs = sorted(
              zip(nodes[index][3].keys(), np.true_divide(nodes[index][3].values(), np.sum(nodes[index][3].values()))),
              key=itemgetter(1), reverse=True)
          if prediction == y:
              margin = probs[0][1] - probs[1][1] if len(probs) > 1 else 1
          else:
              margin = dict(probs).get(y, 0) - probs[0][1]
          return node_id, margin