How to find a value from a Binary Search Tree in python?

Question

I want to create a interactive Binary Search Tree(BST). So I created the BST using the following code as

class BTreeNode(object):
 def __init__(self, data):
 self.data = data
 self.rChild = None
 self.lChild = None
 def __str__(self):
 return (self.lChild.__str__() + '<-' if self.lChild != None 
 else '') + self.data.__str__() + (
 '->' + self.rChild.__str__() if self.rChild != None else '')
 # Insert method to create nodes
 def insert(self, btreeNode):
 if self.data > btreeNode.data: # insert left
 if self.lChild == None:
 self.lChild = btreeNode
 else:
 self.lChild.insert(btreeNode)
 else: # insert right
 if self.rChild == None:
 self.rChild = btreeNode
 else:
 self.rChild.insert(btreeNode)
 # Insert method to create nodes
 # findval method to compare the value with nodes
 def findval(self, lkpval):
 if lkpval < self.data:
 if self.lChild.data is None:
 return str(lkpval)+" Not Found"
 return self.lChild.findval(lkpval)
 elif lkpval > self.data:
 if self.rChild.data is None:
 return str(lkpval)+" Not Found"
 return self.rChild.findval(lkpval)
 else:
 print(str(self.data) + ' is found')
 # findval method to compare the value with nodes
def display():
 btreeRoot = BTreeNode(5)
 print('inserted %s:' % 5, btreeRoot)
 btreeRoot.insert(BTreeNode(7))
 print('inserted %s:' % 7, btreeRoot)
 btreeRoot.insert(BTreeNode(3))
 print('inserted %s:' % 3, btreeRoot)
 btreeRoot.insert(BTreeNode(1))
 print('inserted %s:' % 1, btreeRoot)
 # print(btreeRoot.findval(3))
print(display())

If I execute the above code I will get the following interactive output as

inserted 5: 5

inserted 7: 5->7

inserted 3: 3<-5->7

inserted 1: 1<-3<-5->7

This is the my expected output and I got it. Also, I want to find a value from the BST. So I used the following code in the display function as

# print(btreeRoot.findval(3))

If I un comment the code I will get error. So, how can I modify my code to display whether 3 is present in the BST or not? Thanks..

• reartnew: I get no errors running this code. Could you provide a traceback, please?
• user1999109: Please find the unknown value in the BST. For ex. print(btreeRoot.findval(33)) . This time it shows error..

Answer 1

The problem occurs when you perform checks if self.lChild.data is None and if self.rChild.data is None. These lines should be replaced by if self.lChild is None and if self.rChild is None respectively, as your class implies those attributes being None's, not their data attributes.

Also consider using is None instead == None. This is not a big problem in this case, but may cause troubles in other contexts. Look here for details: Python None comparison: should I use "is" or ==?

• user1999109: As per your guidelines now its working.. Thank you very much reartnew..