BST height in python

Question

I have written a class called Node with certain functions to create a binary search tree. All of the functions work correctly except the function height() that is supposed to calculate the height of the BST. It returns a very small number compared to what I was expecting it too given that I haven't balanced the tree. The number I was expecting was close to N where N is the amount of numbers I have entered in the tree. Here is the code:

from __future__ import print_function
import random

class Node(object):

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def lookup(self, data, parent=None):

        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
               return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

    def delete(self, data):

        node, parent = self.lookup(data)
        if node is not None:
            children_count = node.children_count()
            if children_count == 0:

                if parent:
                    if parent.left is node:
                        parent.left = None
                    else:
                        parent.right = None
                else:
                    self.data = None
            elif children_count == 1:

                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                else:
                    self.left = n.left
                    self.right = n.right
                    self.data = n.data
            else:

                parent = node
                successor = node.right
                while successor.left:
                     parent = successor
                     successor = successor.left

                node.data = successor.data

                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right

    def compare_trees(self, node):

        if node is None:
            return False
        if self.data != node.data:
            return False
        res = True
        if self.left is None:
            if node.left:
                return False
        else:
            res = self.left.compare_trees(node.left)
        if res is False:
            return False
        if self.right is None:
            if node.right:
                return False
        else:
            res = self.right.compare_trees(node.right)
        return res

    def print_tree(self):

        if self.left:
            self.left.print_tree()
        print(self.data, end=" ")
        if self.right:
            self.right.print_tree()

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



random.seed(3)



bst = Node(random.randint(1,1000)) 
for i in range(1,80000,1):
    bst.insert(random.randint(1,1000))

print(bst.height(bst))

Are you sure it's wrong? I don't see why the height should necessarily be close to N, even before it's balanced. — glibdud
This is the expected answer of an exercise I have been given as homework. I know the height can be much smaller than N but it all depends on the order of wich the elements are inserted in the tree structure. Having tested it for many cases and always getting a relatively small number as a result, i think I have made a mistake somewhere in either my code or logic. — Shivalnu
Getting a height "close" to N is actually pretty improbable. It would require that the random string of numbers you populate the list with to be close to sorted already. — glibdud
That is true. But getting a tree height of 41 while inputting 80000 random integers from 1 to 1000000000000 is equally unlikely, isn't it? Am I missing something? — Shivalnu

Tilak Putta Tilak Putta · Accepted Answer · 2017-03-14T16:01:03

You are getting low answer because you are always inserting number from 1 to 1000 only so the numbers existing are always remains same and you are thinking you are inserting 1,80000 numbers but actually because of generating randomly the same numbers from 1 to 1000 you are actually inserting just 1000 values from 1 to 1000 maximum.

Wrong Code

bst = Node(random.randint(1,1000)) 
for i in range(1,80000,1):
    bst.insert(random.randint(1,1000))

print(bst.height(bst))

Modification

bst = Node(random.randint(1,80000)) 
for i in range(1,80000,1):
    bst.insert(random.randint(1,80000))

print(bst.height(bst))

Your code is working fine you can execute below code and check it with the image below

bst = Node(7)
list1 = [3,11,1,5,9,13,4,6,8,12,14,8.5]
for i in list1:
    bst.insert(i)
print(bst.height(bst))
bst.print_tree()

Ouput

5
1 3 4 5 6 7 8 8.5 9 11 12 13 14

BST height in python

2 Answers