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

I get no errors running this code. Could you provide a traceback, please? — reartnew, Dec 02 '18 at 06:20
Please find the unknown value in the BST. For ex. print(btreeRoot.findval(33)) . This time it shows error.. — user1999109, Dec 02 '18 at 12:41

score 1 · Accepted Answer · answered Dec 02 '18 at 13:21

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 ==?

As per your guidelines now its working.. Thank you very much reartnew.. — user1999109, Dec 02 '18 at 14:20

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

1 Answers1