python binary search tree

Question

For some reason, I can't seem to get the "find" method to work. I think it has to do with a scoping issue... the root.val doesn't seem to update globally. I get an error message saying AtributeError: 'int' object has no attribute 'val' Here is my code at the moment:

class BinaryNode:
    def __init__(self, v):
        self.val = v
        self.leftChild = None
        self.rightChild = None
    def get(self):
        return self.val
    def set(self, v):
        self.val = v
    def getChildren(self):
        children = []
        if self.leftChild != None:
            children.append(self.leftChild)
        if self.rightChild != None:
            children.append(self.rightChild)
        return children

class Tree:
    def __init__(self):
        self.root = None
    def setRoot(self, node):
        self.root = node
    def size(self):
        if self.root == None:
            return 0
    def subtreeSize(node):
        return 1 + sum(subtreeSize(c) for c in node.getChildren())
        return subtreeSize(self.root)

class BinarySearchTree(Tree):
    def insert(self, val):
        self.insertNode(self.root, val)

    def insertNode(self, node, val):
        if node is None:
            self.setRoot(BinaryNode(val))
        elif val <= node.val:
            node.leftChild = insertNode(BinaryNode(val), val)
        elif val > node.val:
            node.rightChild = insertNode(BinaryNode(val), val)
        else:
            node.val = val


    def find(self, val):
        self.findNode(self.root, val)

    def findNode(self, node, val):
        if node is None:
            return False
        elif val == node.val:
            return True
        elif val < node.val:
            self.findNode(val, node.leftChild)
        else:
            self.findNode(val, node.rightChild)


if __name__ == "__main__":
    btree = BinarySearchTree()
    vals = [5]
    for v in vals:
        btree.insert(v)
    tests = [8, 5]
    for t in tests:
        print "find(%i) = %s" % (t, ("True" if btree.find(t) else "False"))

Answer 1

There are two problems with your findNode() method:

1. You swapped the node and val arguments when you call it recursively. This causes your code to try to look up .val on the integer value instead of the node.

2. You forgot to return the recursive call results.

Corrected methods:

def find(self, val):
    return self.findNode(self.root, val)

def findNode(self, node, val):
    if node is None:
        return False
    elif val == node.val:
        return True
    elif val < node.val:
        return self.findNode(node.leftChild, val)
    else:
        return self.findNode(node.rightChild, val)

Your next problem is your insertNode method; you try to call a global insertNode() function in it; that should probably be self.insertNode() instead. However, that method has no return value, so you end up setting node.leftChild or node.rightChild to None.

You want to just hand over the search for the insertion point to a recursive call, no need to use a return value:

def insert(self, val):
    if self.root is None:
        self.setRoot(BinaryNode(val))
    else:
        self.insertNode(self.root, val)

def insertNode(self, node, val):
    if val <= node.val:
        if node.leftChild:
            self.insertNode(node.leftChild, val)
        else:
            node.leftChild = BinaryNode(val)
    elif val > node.val:
        if node.rightChild:
            self.insertNode(node.rightChild, val)
        else:
            node.rightChild = BinaryNode(val)

With these changes, your simple test prints:

find(8) = False
find(5) = True

Answer 2

One problem with findNode() is that you are missing return statements. The

    elif val < node.val:
        self.findNode(val, node.leftChild)
    else:
        self.findNode(val, node.rightChild)

should read

    elif val < node.val:
        return self.findNode(val, node.leftChild)
    else:
        return self.findNode(val, node.rightChild)

You have a similar problem in insertNode().