Clash Royale CLAN TAG

Python: Using recursive methods to get Binary Search Tree Height

for my assignment, I am trying to get height of the Binary Search Tree through linear time. The prof specified that he wants us to keep track of the height in our recursive insertion and removal methods, yet mine never works during the test.

The prof's requirement is: "Add an attribute to the __Node class to store the height of the subtree rooted at that node. Just before returning a node reference at the end of a recursive call, update that node's height field to be correct."

My thought is, instead of making changes at a root, if the insertion or removal moves down left or right, the height increases/decrease by one (but I'm not sure how it works if there is still something left at level-n).

I have attached my code over here:

class Binary_Search_Tree:

class __BST_Node:

def __init__(self, value):
self.value = value
self.left=None
self.right=None
self.height=0

def __init__(self):
self.__root = None

def __recur_ins(self, val,root):
if root is None:
root = Binary_Search_Tree.__BST_Node(val)
elif root.value > val:
root.left = self.__recur_ins(val,root.left)
root.height += 1
elif root.value < val:
root.right =self. __recur_ins(val,root.right)
root.height += 1
return root

def __get_min(self,node):
walker=node
while walker.left is not None:
walker=walker.left
return walker

def __recur_rem(self, val, root):
if root is None:
raise ValueError
if root.value == val:
if root.left is None:
cur = root.right
root = None
return cur
elif root.right is None:
cur = root.left
root = None
return cur
elif (root.left is not None) and (root.right is not None):
cur = self.__get_min(root.right)
root.value = cur.value
root.right = self.__recur_rem(cur.value, root.right)
elif val < root.value:
root.left=self.__recur_rem(val,root.left)
root.height -= 1
elif val > root.value:
root.right=self.__recur_rem(val, root.right)
root.height -= 1
return root

def __actual_height(self,bst_node):
if bst_node is None:
return 0
else:
return self.__root.height

def get_height(self):
return self.__actual_height(self.__root)


Thank you so much in advance! Any help will be very appreciated!

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.