CODEWITHSUNDEEP
pythonrecursionbinary-tree
Tova
Tova

Reputation: 25

problem with list in recursion for traversing binary tree

I'm trying to use recursion to traverse a binary tree. Each tree either has two children, or it has no children (that is, the fields reserved for children == None)

I'd like to add the final leaves of each branch (that is, each Node whose two children == None) to a list, and return the list. I'm doing this with the 'search' function, and the helper 'search_base' function.

Through the debugger, I see that the list within the 'search' function indeed contains the elements I want it to. But, when it's returned in the search_base function, the result seems to be an empty list.

I'm extremely confused and would be grateful for any help. Thank you! 

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

class Diagnoser:
    def __init__(self, root):
        self.root = root

    def search_base(self):
        leaf_list=[]
        current = self.root
        return self.search(current, leaf_list)

    def search(self, current, leaf_list):
        if(current.positive_child == None):
            leaf_list.append(current)
            return leaf_list
        else:
            self.search(current.positive_child, leaf_list)
            self.search(current.negative_child, leaf_list)


if __name__ == "__main__":

    # Manually build a simple tree.
    #                cough
    #          Yes /       \ No
    #        fever           healthy
    #   Yes /     \ No
    # influenza   cold

    flu_leaf = Node("influenza", None, None)
    cold_leaf = Node("cold", None, None)
    inner_vertex = Node("fever", flu_leaf, cold_leaf)
    healthy_leaf = Node("healthy", None, None)
    root = Node("cough", inner_vertex, healthy_leaf)

    diagnoser = Diagnoser(root)
    leaf_list = diagnoser.search_base()
    print(leaf_list[0].data)

Upvotes: 0

Views: 100

Answers (3)

Alex Hall
Alex Hall

Reputation: 36033

Here's a full simpler solution without side effects:

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

    def leaves(self):
        if self.positive_child is self.negative_child is None:
            return [self]
        else:
            return (self.positive_child.leaves() +
                    self.negative_child.leaves())


if __name__ == "__main__":
    # Manually build a simple tree.
    #                cough
    #          Yes /       \ No
    #        fever           healthy
    #   Yes /     \ No
    # influenza   cold

    flu_leaf = Node("influenza", None, None)
    cold_leaf = Node("cold", None, None)
    inner_vertex = Node("fever", flu_leaf, cold_leaf)
    healthy_leaf = Node("healthy", None, None)
    root = Node("cough", inner_vertex, healthy_leaf)
    for leaf in root.leaves():
        print(leaf.data)

Upvotes: 0

Aaron Zolnai-Lucas
Aaron Zolnai-Lucas

Reputation: 207

The problem is that in 

self.search(current.positive_child, leaf_list)
self.search(current.negative_child, leaf_list)

The return values from these statements is not saved or returned, so here the function gives None. Also, the leaf_list passed into both these statements is the same, i.e., they don't get concatenated. In recursive functions you it's best not to have side effects to keep it safe. It should be:

 def search(self, current, leaf_list=[]):
        if(current.positive_child == None):
            return [current]
        else:
            return (self.search(current.positive_child, leaf_list)
                    + self.search(current.negative_child, leaf_list))

Upvotes: 2

Alex Hall
Alex Hall

Reputation: 36033

Since search modifies the list, it doesn't need to return anything, and search_base can just return the modified list.

class Diagnoser:
    def __init__(self, root):
        self.root = root

    def search_base(self):
        leaf_list = []
        current = self.root
        self.search(current, leaf_list)
        return leaf_list

    def search(self, current, leaf_list):
        if current.positive_child is None:
            leaf_list.append(current)
        else:
            self.search(current.positive_child, leaf_list)
            self.search(current.negative_child, leaf_list)

Also, you need to check that both children are missing, i.e.

if current.positive_child is None and current.negative_child is None:

Upvotes: 0

Related Questions