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