python-coder - 3 months ago 30
Python Question

# how to calculate the height of a BST in python

I've created a BST. and now I want to find the height of the BST developed.

Here is my code for constructing the BST

``````class Node:
'''represents a new node in the BST'''
def __init__(self,key):
self.key=key
self.disconnect()
def disconnect(self):
self.left=None;
self.right=None;
self.parent=None;
def __str__(self):
return 'node with kay %s'%self.key

class BST:
def __init__(self):
self.root=None

def insert(self,t):
'''inserts a new element into the tree'''
if self.root is None:
self.root = Node(t)
else:
self._do_insert(self.root,t)

def _do_insert(self,parent,t):
if t > parent.key:
if parent.left is None:
parent.left = Node(t)
else:
self._do_insert(parent.left,t)
elif t < parent.key:
if parent.right is None:
parent.right = Node(t)
else:
self._do_insert(parent.right,t)
else:
# raise a KeyError or something appropriate?
pass
``````

I've a list of numbers (
`[2,4,6,3,190,1,56 and so on]`
) via which this BST is constructed.

Now I want to find the height of the BST created. How can I do that?

EDIT

As per the solution provided I tried this :-

``````def create_bst(values):

'''Creates a BST and returns the BST created object'''
BSTobj = BST()

for i in values:
BSTobj.insert(i)

return BSTobj

def height_of_BST(bst):

'''Returns the height of the BST created'''
if bst == None: return 0
else: return 1 + max(height_of_BST(bst.left), height_of_BST(bst.right))

print height_of_BST(create_bst(unique_values))
``````

And its not working. It pops up an error saying
`BST instance has no attribute 'left'`

``````def height(bst):