I Understand this type of questions have been asked before and I am not blindly asking you guys this question as I have went through previous questions and I quite did not get it. This is the code below:
class Node():
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class BST():
def __init__(self):
self.head=None
def insert(self,data):
if self.head is None:
self.head=Node(data)
if self.head:
if data<self.head.data:
if self.head.left is None:
self.head.left=Node(data)
else:
self.head.left.insert(data)
if data>self.head.data:
if self.head.right is None:
self.head.right=Node(data)
else:
self.head.right.insert(data) #Actual error point
l1=BST()
l1.insert(2)
l1.insert(4)
l1.insert(6) #Getting the error while inserting this
I understand I either need to put the insert method inside Node class or inherit the Node class properties in to BST class but I am having hard time to implement both solutions, could you guys please walk me through both solutions, an explanation with written code would be really helpful to me .
You might be tired of seeing these questions, you are all experts here and you know how hard it could be for a beginner and especially I don't want to start off with unclear concepts.
One way to solve the problem is to give Nodes a method to attach another to it based on how its value compares to its own and have the tree class call it. The tree class instance can then just call its head Node to do this. The code below shows how to do that.
Notably, I've also changed the tree class so one will never be empty by making the head a Node with a unique data value when it's created. Doing this means the only time a check for an empty tree needs to be done is when a TypeError is raised when trying to attach data to the tree — instead of over-and-over again, recursively, in the Node.attach() method. Implement it this way makes the code simpler and run faster. The check is done by seeing if the tree's head is not a special value which couldn't possibly be real data.
Such special values are referred to as "sentinel values" and it's important to make sure they're distinguishable from any possible legal value. In Python you can create an instance of the built-in (largely featureless) object class to do get one.
class BinaryTree:
SENTINEL = object() # Unique value.
def __init__(self):
self.head = Node(self.SENTINEL)
def insert(self, data):
try:
self.head.attach(data)
except TypeError:
if self.head.data is self.SENTINEL: # Empty tree?
self.head.data = data # First is special case.
else:
raise
def print(self):
self.head.print()
print()
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def attach(self, data):
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.attach(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.attach(data)
def print(self):
if self.left:
self.left.print()
print(self.data, end=' ')
if self.right:
self.right.print()
if __name__ == '__main__':
tree = BinaryTree()
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.print() # -> 2 4 6