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"))

Why would you delete the question and deny others the help that you received? — Gareth
– Gareth, Commented Apr 12, 2013 at 9:40
Please, do not remove the question. You posted this under the CC Wiki license (see bottom right of the page) and your question is meant to help others in the future too. — Martijn Pieters
– Martijn Pieters, Commented Apr 12, 2013 at 9:42
If you feel you posted this in error (don't want your professor to find out?) then you need to request to be disassociated from the post. Do not simply vandalize it and deny those that helped you the reputation and recognition. — Martijn Pieters
– Martijn Pieters, Commented Apr 12, 2013 at 9:44

Martijn Pieters · Accepted Answer · 2013-04-12 09:25:08Z

There are two problems with your findNode() method:

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.
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

(+1) Well spotted on the swapped arguments. I've been puzzling over the exception, and this explains it.
@BobertHido: Not helpful enough, I take it? Anything else wrong? I tested the code a little more, it works for me as it stands now.

NPE · Accepted Answer · 2013-04-12 08:52:52Z

0

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().

answered Apr 12, 2013 at 8:52

NPE

503k114 gold badges970 silver badges1k bronze badges

Collectives™ on Stack Overflow

python binary search tree

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related