python-coder 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'

Answer

The height of a nonempty binary search tree is 1 + the height of its tallest subtree, or just 1 if it has no children. This translates pretty directly to a recursive algorithm. In pseudocode:

def height(bst):
    if isempty(bst):
        return 0
    else:
        return 1 + max(height(bst.left), height(bst.right))
Comments