python-coder - 1 year ago 129

Python Question

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]`

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

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 Source

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))
```