The implementation for BST with Python

BST.py

#! /usr/bin/env python3

# implementation of a binary search tree

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, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(data, self.root)
    
    def _insert(self, data, cur_node):
        if data < cur_node.data:
            if cur_node.left is None:
                cur_node.left = Node(data)
            else:
                self._insert(data, cur_node.left)
        elif data > cur_node.data:
            if cur_node.right is None:
                cur_node.right = Node(data)
            else:
                self._insert(data, cur_node.right)
        else:
            print("Value already in tree!")
    
    def find(self, data):
        if self.root:
            is_found = self._find(data, self.root)
            if is_found:
                return True
            return False
        else:
            return None
    
    def _find(self, data, cur_node):
        if data > cur_node.data and cur_node.right:
            return self._find(data, cur_node.right)
        elif data < cur_node.data and cur_node.left:
            return self._find(data, cur_node.left)
        if data == cur_node.data:
            return True
    
    def print_tree(self):
        if self.root is not None:
            self._print_tree(self.root)
    
    def _print_tree(self, cur_node):
        if cur_node is not None:
            self._print_tree(cur_node.left)
            print(str(cur_node.data))
            self._print_tree(cur_node.right)
    
    def height(self):
        if self.root is not None:
            return self._height(self.root, 0)
        else:
            return 0
    
    def _height(self, cur_node, cur_height):
        if cur_node is None: return cur_height
        left_height = self._height(cur_node.left, cur_height + 1)
        right_height = self._height(cur_node.right, cur_height + 1)
        return max(left_height, right_height)
    
    def fill_tree(self, tree, num_elems=100, max_int=1000):
        from random import randint
        for _ in range(num_elems):
            cur_elem = randint(0, max_int)
            tree.insert(cur_elem)
        return tree
    
    def size(self):
        if self.root is not None:
            return self._size(self.root)
        else:
            return 0
    
    def _size(self, cur_node):
        if cur_node is None: return 0
        return 1 + self._size(cur_node.left) + self._size(cur_node.right)
    
    def delete_value(self, data):
        return self.delete_node(self.find(data))
    
    def delete_node(self, node):
        # -----
        # Improvements to be made
        # -----
        if node is None or self.find(node.data) is False:
            print("Node to be deleted not found in the tree!")
            return None
        
        def min_value_node(n):
            current = n
            while current.left is not None:
                current = current.left
            return current
        
        def num_children(n):
            num_children = 0
            if n.left is not None: num_children += 1
            if n.right is not None: num_children += 1
            return num_children
        
        # get the parent of the node to be deleted
        node_parent = node.parent
        
        # get the number of children of the node to be deleted
        node_children = num_children(node)
        
        # break operation into different cases based on the
        # structure of the tree & node to be deleted
        # Case 1 (node has no children)
        if node_children == 0:
            # remove reference to the node from the parent
            if node_parent.left is node:
                node_parent.left = None
            else:
                node_parent.right = None
        
        # Case 2 (node has a single child)
        if node_children == 1:
            # get the single child node
            if node.left is not None:
                child = node.left
            else:
                child = node.right
            
            # replace the node to be deleted with its child
            if node_parent.left is node:
                node_parent.left = child
            else:
                node_parent.right = child
        
        # Case 3 (node has two children)
        if node_children == 2:
            # get the inorder successor of the deleted node
            successor = min_value_node(node.right)
            
            # copy the inorder successor's value to the node formerly
            # holding the value we wished to delete
            node.data = successor.data
            
            # delete the inorder successor now that it's value was
            # copied into the other node
            self.delete_node(successor)
    
    def search(self, val):
        if self.root:
            return self._search(val, self.root)
        else:
            return False
    
    def _search(self, val, cur_node):
        if val < cur_node.data:
            if cur_node.left is None:
                return False
            return self._search(val, cur_node.left)
        elif val > cur_node.data:
            if cur_node.right is None:
                return False
            return self._search(val, cur_node.right)
        else:
            print("Found: ", cur_node.data)
            return True
    
    def is_bst_satisfied(self):
        """
        Returns True if the tree is a valid binary search tree
        """
        if self.root:
            is_satisfied = self._is_bst_satisfied(self.root, self.root.data)
            
            if is_satisfied is None:
                return True
            return False
        return True
    
    def _is_bst_satisfied(self, cur_node, data):
        if cur_node.left:
            if data > cur_node.left.data:
                return self._is_bst_satisfied(cur_node.left, cur_node.left.data)
            else:
                return False
        
        if cur_node.right:
            if data < cur_node.right.data:
                return self._is_bst_satisfied(cur_node.right, cur_node.right.data)
            else:
                return False

if __name__ == '__main__':
    # testcase
    tree = BinarySearchTree()
    tree = tree.fill_tree(tree)
    tree.print_tree()
    print("Tree height: ", tree.height())
    print("Tree size: ", tree.size())
    print("Is BST satisfied? ", tree.is_bst_satisfied())