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

Answer 1

 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.

Answer 2

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)