BST (Binary Search Tree) element filter function keeps encountering 'NoneType' object

user_14457622 0
Viewed 315

I'm currently stuck on this exercise where I have to filter a binary search tree by returning a list that contains filtered values. This is the exercise:

Given a binary search tree of integers, create a function that will return the elements in a list, where each element x satisfies: a <= x < b, where a and b are parameters provided to the function.

filter_bst(tree_node, a, b)

For example, if we insert the values from 0 to 10 into the tree tree_node then filter_bst(tree_node, a, b) will return [3,4,5].

We have this module called bst.py (which has the code for binary search tree) in our exercise:

class TreeNode(object):
    """A tree node with two children trees"""

    def __init__(self, data, parent=None, left=None, right=None):
        self.data = data
        self.parent = parent
        self.left = left
        self.right = right

    def search(self, value):
        """Search in a BST"""
        if self.data is None:
            return None

        if self.data == value:
            return self

        if value < self.data:
            if self.left is None:
                return None
            return self.left.search(value)

        else:
            if self.right is None:
                return None
            return self.right.search(value)

    def insert(self, value):
        """insert a node in a BST"""
        if self.data is None:
            self.data = value
            return

        if value < self.data:
            if self.left is None:
                self.left = TreeNode(value, self)
            else:
                self.left.insert(value)

        else:
            if self.right is None:
                self.right = TreeNode(value, self)
            else:
                self.right.insert(value)

I tried this code, but it isn't working:

import bst

def filter_bst(tree_node, a, b):
    l = []
    def filter(tree_node, a, b,l):
        if tree_node is None:
            return l

            # Since the desired output is sorted, recurse for left
            # subtree first. If tree_node.data is greater than a, then
            # only we can get output keys in the left subtree
        if a < tree_node.data:
            filter(tree_node.left, a, b, l)

            # If tree_node's data lies in range, then prints its data
        if a <= tree_node.data and b > tree_node.data:
            l += [tree_node.data]

            # If tree_node.data is smaller than b, then only we can get
            # o/p keys in right subtree
        if b > tree_node.data:
            filter(tree_node.right, a, b, l)
    return filter(tree_node, a, b, l)

root = bst.TreeNode(1)
root.insert(2)
root.insert(3)
root.insert(4)
root.insert(5)
filter_bst(root,2,5)

It's telling me that: 'NoneType' object is not iterable.

PS: I also tried this following code as well but it's also not working:

import bst

def filter_bst(tree_node,a,b):
    l = []
    for temp in range(a,b):
        if tree_node.search(temp) is not None:
            l += [temp]
    return l

root = bst.TreeNode(1)
root.insert(2)
root.insert(3)
root.insert(4)
root.insert(5)
filter_bst(root,2,5)

It's telling me that: 'NoneType' object has no attribute 'search'

binary-search-tree python
1 Answers

Your function almost always returns None. The exception you're getting is not from the code you've shown, but from some other code that is trying to consume the returned list and fails when it gets None instead. The issue is that your inner recursive function doesn't return anything from its recursive cases (only from the base case) and the outer function returns the result of calling the inner function. You can avoid this by never having the inner function return anything (it only has side effects, adding values to l), and returning l from the outer function.

def filter_bst(tree_node, a, b):
    l = []
    def filter(tree_node, a, b,l):
        if tree_node is None:
            return                       # this base case is now just bailing out early

        if a < tree_node.data:
            filter(tree_node.left, a, b, l)

        if a <= tree_node.data and b > tree_node.data:
            l += [tree_node.data]

        if b > tree_node.data:
            filter(tree_node.right, a, b, l)
    filter(tree_node, a, b, l)           # don't return here, filer always returns None
    return l                             # but that's ok because we can return the right thing

That solves your actual issue, but you could further simplify your code a bit. I'd start by noting that you don't actually need to pass in variables to the inner function if they're already bound to the right thing in the outer function (and don't need to be reassigned at any point). You could use this for a, b and l, so you'd only need one argument: filter(tree_node).

A few minor style tweaks I'd suggest: l is a very bad variable name because it looks quite a lot like the digit 1 in many fonts (and like capital I in some others). A longer variable name that is more specific, like result would be a lot better. You might also want to change a and b to lower_bound and upper_bound or something, so that their meaning is immediately clear.

And there's no need to pack a single value into a list to extend it onto another list. You should just write l += [tree_node.data] as l.append(tree_node.data).

user_14050650
Related