Trouble recursively building a binary decision tree python

Question

I'm trying to recursively build a binary decision tree, for diagnosing diseases in python 3. The builder takes a list of records (each is an illness and a list of its symptoms), and a list of symptoms, shown bellow:

class Node:
    def __init__(self, data = "", pos = None, neg = None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg
class Record:
    def __init__(self, illness, symptoms):
        self.illness = illness
        self.symptoms = symptoms

records= [Record('A',['1','3']),
          Record('B',['1','2']),
          Record('C',['2','3']),
          ]
symptoms = ['1','2','3']

And builds a binary tree, each level checks if symptom is true, or false, with a child node for each one. The right child is always means the symtom is not present and the left one that it is present. For the example data the tree should look like this:

                       1
               2                    2
          3        3          3            3
    None   B     A   None   C  None   None     Healthy

For example, the leaf A is reached by asking: 1 : True 2 : False 3 : True and it's path is [1,3] (the trues)

Here is the code I'm using, but isn't working:

def builder(records, symptoms, path):
    #Chekl if we are in a leaf node that matches an illness
    for record in records:
        if path == record.symptoms:
            return Node(record.illness,None,None)

     #No more symptoms means an empty leaf node
    if len(symptoms) == 0:
        return Node(None,None,None)

    #create subtree
    else:
        symptom = symptoms.pop(0)
        right_child = builder(records,symptoms,path)
        path.append(symptom)
        left_child = builder(records,symptoms,path)
        return  Node(symptom,right_child,left_child)

I tried a cold run, and in paper it worked fine. I'm not sure of what I'm missing, but the resulting tree has a lot of empty nodes, and not one with the illness. Maybe I'm messing up the path thing, but I'm not sure how to fix it right now.

"it isn't working' isn't really precise. What does not work the way you wanted? If I print print(builder(records,symptoms,['1','3']).data) as you described I'm getting A. — Banana

Davis Herring Davis Herring · Accepted Answer · 2018-01-07T06:38:08

Your symptoms.pop(0) is affecting the one symptoms list shared by all calls to builder. This is fine on the way down, since you want to consider only the subsequent symptoms. But when a recursive call returns, your list is missing elements. (If it returns without finding a match, it’s empty!) Similarly, the shared path keeps growing forever.

The simple if inefficient answer is to make new lists when recursing:

symptom=symptoms[0]
symptoms=symptoms[1:]
path=path+[symptom]  # not +=

Trouble recursively building a binary decision tree python

1 Answers