import random

class BSTNode(object):
    """
    Implementation for the node of Binary Search Tree
    """

    def __init__(self, key, content, parent=None, left=None, right=None):
        """
        The class constructor
        @param key: the key of the node
        @param content: the content of the node
        @param parent: pointer to the parent node
        @param left: pointer to the left child
        @param right: pointer to the right child
        @return: None
        """
        self.key = key
        self.content = content
        self.parent = parent
        self.left = left
        self.right = right


class BinarySearchTree(object):
    """
    Implementation for Binary Search Trees
    """

    def __init__(self):
        """
        The class constructor
        @return: None
        """
        self.root = None
        self.size = 0

    def print_subtree(self, node):
        """
        Print tree content in order of the keys from node
        @return: None
        """
        return None

    def print_tree(self):
        """
        Print tree content in order of the keys
        @return: None
        """

        return None
        
        
    def find_recursive(self, node, key):
        """
        Search the key from node, recursively
        @param node: a BST Node
        @param key: a key value
        @return: the node with the key; None if the key is not found
        """
        return None

    def find_iterative(self, node, key):
        """
        Search the key from node, iteratively
        @param node: a BST Node
        @param key: a key value
        @return: the node with the key; None if the key is not found
        """
        return None

    def search(self, key):
        """
        Find the node with the key
        @param key: the target key
        @return: the node with the key; None if the key is not found
        """
        return None

    def insert(self, key, content):
        """
        Insert the (key, content) to the BST
        @param key: the key to insert
        @param content: the content to insert
        @return: True if insert successfully; otherwise return False
        """
        return None

    def replace_node(self, node, new_node):
        """
        Replace the node by new_node, update in its parent node
        @param node: node to replace
        @param new_node: the new node
        @return: None
        """
        return None
        
    def remove_node(self, node):
        """
        Remove the node from the tree
        @param node: the node to remove
        @return: None
        """
        return None

    def delete(self, key):
        """
        Delete the node with the key
        @param key: a key value
        @return: The key deleted, None if key does not exist
        """
        return None

# Partie principale du programme:
#################################

keys = [1, 2, 3, 4, 5, 6]
random.shuffle(keys)
bst = BinarySearchTree()
# Cas particulier où content correspond à key
for k in keys:
    bst.insert(k,k)

print("Contenu de l'arbre initial: ")
bst.print_tree()

random.shuffle(keys)
for k in keys:
    print("\nNoeud à enlever: ")
    print(bst.search(k).content)
    bst.delete(k)
    print("Noeuds restants: ")
    bst.print_tree()