def predict(tree, x, y=[], dist=False):
    """
    Function makes a prediction of one sample with a tree model. If y label is defined it returns node identifier and margin.

    tree: dictionary - tree model
    x: numpy array - one sample from the dataset
    y: string, integer or float - sample label
    """

    # conditions of continuous and discrete features
    node_id = 1  # initialize node identifier as first node under the root
    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]  # set identifier of child node
            else:
                index, node_id = 1, nodes[1][0]  # set identifier of child node
        else:
            if x[nodes[0][1]] in nodes[0][2]:
                index, node_id = 0, nodes[0][0]  # set identifier of child node

            elif x[nodes[1][1]] in nodes[1][2]:
                index, node_id = 1, nodes[1][0]  # set identifier of child node

            else:
                # value is not in left or right branch. Get label distributions of left and right child
                # sum labels distribution to get parent label distribution
                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():  # check if tree can be traversed further
            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
Function makes a prediction of one sample with a tree model. If y label is defined it returns node identifier and margin.

    tree: dictionary - tree model
    x: numpy array - one sample from the dataset
    y: string, integer or float - sample label