Calculating Range from Binary Search Tree

Question

Is there a more suitable way to retrieve a range (difference between highest and lowest number) from this Binary Search Tree? I've tried returning the difference between the max & min value in the range function but nothing is working.

Here's my code:

# %load bst.py


class Node:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        # self.parent = None


class BST:
    def __init__(self):
        self.root = None  # the root of the tree

    def insert(self, new_node):
        if self.root is None:  # is the tree empty?
            self.root = new_node  # if yes, new node becomes the root
            return
        self.insertNode(self.root, new_node)

    def insertNode(self, root, new_node):
        if new_node.data > root.data:
            if root.right_child is not None:  # does right child exist?
                self.insertNode(root.right_child, new_node)
            else:
                root.right_child = new_node  # new node becomes right child
                return
        else:  # case where new_node.data <= root.data
            if root.left_child is not None:  # does left child exist?
                self.insertNode(root.left_child, new_node)
            else:  # left child does not exist
                root.left_child = new_node

    # assignment starts here
    def postOrder(self, node):
        if node.left_child is not None:  # does the left child exist?
            self.postOrder(node.left_child)
        if node.right_child is not None:  # checking if right child exists
            self.postOrder(node.right_child)
        print(node.data)  # visit the node

    # finding maxmum of the array
    def findMax(self, node):
        if node.right_child is not None:  # does the right child exist?
            return self.findMax(node.right_child)
        print(node.data)  # visit the node

    # finding minmum of the array
    def findMin(self, node):
        if node.left_child is not None:  # check if left child exist
            return self.findMin(node.left_child)
        print(node.data)  # visit the node

    # finding range
    def range(numbers=[8, 87]):
        import statistics

        statistics.range
        return max(numbers) - min(numbers)


my_bst = BST()
l = [31, 67, 26, 29, 50, 15, 58, 8, 49, 87, 20]
for n in l:
    n1 = Node(n)
    my_bst.insert(n1)

print('maxmum of the array is')
my_bst.findMax(my_bst.root)
print('minmum of the array is')
my_bst.findMin(my_bst.root)
print('postOrdering the array follows')
my_bst.postOrder(my_bst.root)
print('range is')
my_bst.range(my_bst.root)

I've attempted but I keep getting the following error:

Traceback (most recent call last):
  File "main.py", line 76, in <module>
    my_bst.range(my_bst.root)
TypeError: range() takes from 0 to 1 positional arguments but 2 were given`

Answer 1

You design doesn't make much sense. The reason you would have a separate BST class is so that you can write methods over trees that don't rely on recursion. If you're going to rely on recursion, then it makes more sense to just have a Node class, because every node is itself a binary tree.

Here's how I would rewrite the findMin, findMax and range methods of BST

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
    def insert(self, value):
        if self.root is None:
            self.root = Node(value) 
        else:
            curr_node = self.root
            while True:
                if value < curr_node.data:
                    if curr_node.left is None:
                        curr_node.left = Node(value)
                        return
                    else:
                        curr_node = curr_node.left
                elif value > curr_node.data:
                    if curr_node.right is None:
                        curr_node.right = Node(value)
                        return
                    else:
                        curr_node = curr_node.right
                else:
                    return
    def min(self):
        if self.root is None:
            raise TypeError("Empty Tree")
        curr_node = self.root
        while curr_node.left is not None:
            curr_node = curr_node.left
        return curr_node.data
    def max(self):
        if self.root is None:
            raise TypeError("Empty Tree")
        curr_node = self.root
        while curr_node.right is not None:
            curr_node = curr_node.right
        return curr_node.data
    def range(self):
        return self.max() - self.min()


my_bst = BST()
l = [31, 67, 26, 29, 50, 15, 58, 8, 49, 87, 20]
for v in l:
    my_bst.insert(v)
 print(my_bst.range())  # 79

Answer 2

The range fonction should be a method, so you need to define the self parameter as the first argument of the function, like this:

class BST:

    [...]

    # finding range
    def range(self, numbers=[8, 87]):
        import statistics

        statistics.range
        return max(numbers) - min(numbers)

Notice that this is not a good practice to have a mutable parameter because it is not in the local scope of the function. You can fix this as bellow:

    def range(self, numbers=None):
        if numbers is None:
            numbers = [8, 87]
        import statistics

        statistics.range
        return max(numbers) - min(numbers)

In short, you can also write:

    # finding range
    def range(self, numbers=None):
        numbers = numbers or [8, 87]
        import statistics

        statistics.range
        return max(numbers) - min(numbers)

It is better to import statistics globally, like this:

import statistics


class BST:

    [...]

    # finding range
    def range(self, numbers=None):
        numbers = numbers or [8, 87]

        statistics.range
        return max(numbers) - min(numbers)

Notice that the statistics.range function is not called because you forget the parenthesis (and the parameters). So this is dead code.

In your main program, you try to call my_bst.range() with a my_bst.root which is a Node instance. So, you'll have a error when calculating max/min on a Node:

Traceback (most recent call last):
  File "...", line 75, in <module>
    my_bst.range(my_bst.root)
  File "...", line 59, in range
    return max(numbers) - min(numbers)
TypeError: 'Node' object is not iterable

You need to develop your algorithm by yourself.