how to calculate the height of a BST in 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]) 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'

user2357112 · Accepted Answer · 2014-01-09 04:09:56Z

11

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

answered Jan 9, 2014 at 4:09

user2357112

286k32 gold badges490 silver badges571 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

python-coder Over a year ago

Thanks for it. I'm quite new to python, hence was not able to decode the pseudocode into actual code. Here what I tried. I inserted the values inside the BST, then returned the BSTobj to this function. I modified it like this def height_of_BST(bst): if bst == None: return 0 else: return 1 + max(height(bst.left), height(bst.right)). How do I represent bst.left and bst.right ?

python-coder Over a year ago

I've edited my question with what I've tried. Kindly have a look at it and please rectify the errors. Thanks

user2357112 Over a year ago

@python-coder: You're pretty close. This algorithm works on nodes, not the BST class. You just need to have a helper function that extracts the BST's root and passes it to the height function. Something like def height(self): return node_height(self.root).

python-coder Over a year ago

How do I extract the root of the BSt? Do I need to walk down the BST? I didnt understood. Can you please provide a sample code? Thanks!!!

user2357112 Over a year ago

@python-coder: The root of the BST is self.root. No traversal needed; just access the root attribute.

|

reem · Accepted Answer · 2014-01-09 05:40:38Z

1

The BST in your class is actually stored in BST.root not in BST. You need to modify your code to look at BST.root instead of BST.

Try:

def height(BST):
    return actual_height(BST.root)
def actual_height(bst_node):
    if bst_node is None:
        return 0
    else:
        return 1 + max(actual_height(bst_node.left), actual_height(bst_node.right))

This defines a helper function that does the actual work but lets you just call height on the BST object. In the future, you might just want to only have a Node class because your BST class is basically just a wrapper around the root value.

answered Jan 9, 2014 at 5:40

reem

7,2764 gold badges22 silver badges30 bronze badges

Comments

thierno · Accepted Answer · 2018-04-04 10:51:00Z

0

The interpreter is complaining because you didn't check for cases where the node has no children. If a node has no children it heigth is -1 here a solution

def height(bst): if bst == None : return -1 else: return 1 + max(height(bst.left), height(bst.right))

answered Apr 4, 2018 at 10:51

thierno

93411 silver badges10 bronze badges

1 Comment

Andre Simon Over a year ago

root has height 1.

dckuehn · Accepted Answer · 2016-08-22 19:21:25Z

-1

You can use hasattr to check if the object has the attr, if not you get to the end of the tree

def height(bst_node):
     if not hasattr(bst_node, 'left') or not hasattr(bst_node, 'right'):
         return 0
    else:
        return 1 + max(height(bst_node.left), height(bst_node.right))

edited Aug 22, 2016 at 19:21

dckuehn

2,4953 gold badges29 silver badges37 bronze badges

answered Aug 22, 2016 at 18:04

narfeta

1

Collectives™ on Stack Overflow

how to calculate the height of a BST in python

4 Answers 4

8 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

8 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related