0

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)
Improve this question
2
  • You should use is None rather than == None, by the way. Explained here. Commented Feb 5, 2020 at 12:55
  • search doesn't always return something, so return self.search(current, leaf_list) is sometimes going to return None. Commented Feb 5, 2020 at 12:57

3 Answers 3

Reset to default
2

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))
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

"The first line here returns so the second is never executed." there is no return in the first line.
Also both appending and concatenating will cause several nodes to be duplicated, at least with OP's implementation of search_base.
Yeah, my description was inaccurate. The point I was trying to make, was that these values are never returned. Edited to reflect this
It's not just the description, the code is wrong. Test it.
Fixed, the otehr side of the if statement shouldn't return the whole list
|
0

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:
Improve this answer

3 Comments

This worked! Thanks! I understand that I don't NEED to return leaf_list. But, why did doing so give me an incorrect answer?
@Tova see my other comment.
I think between our answers we've got the best solution. The exit points of the function are clearer when the recursive function is a 'pure function' ie has no side effects and returns a value.
0

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)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.