unpredicted output binary search tree in python

Question

class Node(): 
    def __init__(self,data, left=None, right=None): 
        self.data = data 
        self.left = left
        self.right = right 
class BSTree(): 
    def __init__(self): 
        self.root = None
    def add(self,data):
        if self.root is None:
            self.root = Node(data)
            self.reset()
        else:
            while self.curNode is not None:
                if data < self.curNode.data:
                    self.curNode = self.curNode.left
                elif data > self.curNode.data:
                    self.curNode = self.curNode.right
            self.curNode=Node(data)
            self.reset()
    def pprint(self,Node,indent): 
        if Node is not None:
            self.pprint(Node.left, indent+1) 
            print indent*"     ",Node.data
            self.pprint(Node.right, indent+1)  
if __name__=="__main__": 
    y = BSTree() 
    for pres in ["OBAMA","BUSHW","CLINTON","BUSHG","REGAN","CARTER","FORD","NIXON","JOHNSON"]:
        y.add(pres) 
    y.pprint(y.root,0)

This code runs without error but my output is

 OBAMA

I cannot figure out why the code above does not have errors at runtime but only add's the first node to the tree

danben · Accepted Answer · 2010-02-01 17:13:21Z

3

 def __add(self,node,data): 
        if node is None: 
            return Node(data) 
        else: 
            if data < node.data: 
                node.left = self.__add(node.left,data) 
            elif data > node.data: 
                node.right = self.__add(node.right,data)

This function is incorrect. It always overwrites the first left or right child of the root node, unless the root is None.

Since this is homework, I won't write the correct version for you, but here is a hint - first find the spot where the new node should be added, THEN assign to the left or right child.

Edit: in response to your update - you are very close now. Your last error lies in the fact that you are not actually attaching the new node to anything. Rather, you're assigning it to curNode which is not part of the structure of your tree. You instead want to link it to the parent node as either the right or left child.

edited Feb 1, 2010 at 17:13

answered Feb 1, 2010 at 4:40

danben

83.8k18 gold badges127 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Matt Phillips Over a year ago

ok i ended up getting rid of the __add method and the recursion. It looks like python.pastebin.com/m1de4a7c8

danben Over a year ago

Oh, I didn't see the error message at the bottom. That should be self-explanatory - you are checking curNode.left before you check whether curNode is None.

John La Rooy Over a year ago

@danben actually it will be true only when either left or right are None because the and will not test right if left is already a false value. I think it's a confusing expression though

Matt Phillips Over a year ago

changed it to while not(curNode.left and curNode.right) is None. and now i get BUSHG JOHNSON OBAMA REGAN

danben Over a year ago

@gnibbler - that's right, my mistake. @controlfreak123 - you need to take a step back and think about what the actual logic is that you're trying to implement at this part. Update your original post with that and then I'll give you a hint on how to implement it.

|

danben · Accepted Answer · 2010-02-01 18:46:43Z

I figured out the answer. Thank you to danben for guidance in getting there! It was a combination of what he was saying and looking at some other implementations on my own. Here is what I came up with in case anyone was wondering.

class Node(): 
    def __init__(self,data, left=None, right=None): 
        self.data = data 
        self.left = left
        self.right = right 
class BSTree(): 
    def __init__(self): 
        self.root = None

    def __add(self,node,data):
        if self.root is None:
            self.root = Node(data)
        if node is None:
            return Node(data)
        else:
            if data < node.data:
                node.left = self.__add(node.left,data)
            elif data > node.data:
                node.right = self.__add(node.right,data)
            return node

    def add(self,data):
        self.__add(self.root,data)

    def __preorder(self,node): 
        if node is not None:
            print node.data 
            self.__preorder(node.left) 
            self.__preorder(node.right)

    def preorder(self):
        self.__preorder(self.root)

    def __inorder(self,node): 
        if node is not None:
            self.__inorder(node.left)
            self.__inorder(node.right)
            print node.data

    def inorder(self):
        self.__inorder(self.root)

    def __postorder(self,node): 
        if node is not None:
            self.__postorder(node.left)
            print node.data
            self.__postorder(node.right)

    def postorder(self):
        self.__postorder(self.root)

    def pprint(self,Node,indent): 
        if Node is not None:
            self.pprint(Node.right, indent+1) 
            print indent*"     ",Node.data
            self.pprint(Node.left, indent+1) 
    def leafcount(self,Node): 
        if Node is None: 
            return 0 
        if self.atLeaf(Node): 
            return 1 
        else: 
            return self.leafcount(Node.left)+self.leafcount(Node.right) 

if __name__=="__main__": 

    y = BSTree()

    for pres\
        in ["OBAMA","BUSHW","CLINTON","BUSHG","REGAN","CARTER","FORD","NIXON","JOHNSON"]:
        y.add(pres)

    y.pprint(y.root,0)

Collectives™ on Stack Overflow

unpredicted output binary search tree in python

2 Answers 2

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related