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
– reartnew, Commented Dec 2, 2018 at 6:20
Please find the unknown value in the BST. For ex. print(btreeRoot.findval(33)) . This time it shows error.. — user1999109
– user1999109, Commented Dec 2, 2018 at 12:41

reartnew · Accepted Answer · 2018-12-02 13:21:36Z

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

answered Dec 2, 2018 at 13:21

reartnew

2771 silver badge9 bronze badges

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

1 Comment

user1999109 Over a year ago

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

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related