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

class Tree:
    def __init__(self):
        self.root = None

    def DeleteTree(self):
        self.root = None

    def IsEmpty(self):
        return self.root == None

    def PrintTree(self):
        if self.root != None:
            self._PrintTree(self.root)
            print()  # New line after print
        else:
            print("Tree is empty.")

    def _PrintTree(self, node):
        if node != None:
            self._PrintTree(node.left)
            print(str(node.value), end=' ')
            self._PrintTree(node.right)

    def find(self, val):
        if self.root != None:
            return self.findx(val, self.root)
        else:
            print("Tree is empty.")
            return None

    def findx(self, val, node):
        if val == node.value:
            print(f"{node.value} is found")
            return node.value
        elif val < node.value:
            if node.left != None:
                return self.findx(val, node.left)
            else:
                print(f"{val} is not in the tree")
        elif val > node.value:
            if node.right != None:
                return self.findx(val, node.right)
            else:
                print(f"{val} is not in the tree")

    def add(self, val):
        if self.root == None:
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if val < node.value:
            if node.left != None:
                self._add(val, node.left)
            else:
                node.left = Node(val)
        else:
            if node.right != None:
                self._add(val, node.right)
            else:
                node.right = Node(val)

def menu():
    tree = None
    while True:
        print("\nBinary Tree Menu")
        print("1)  Create a Binary Tree")
        print("2)  Delete a Binary Tree")
        print("3)  Check if a Binary Tree is empty")
        print("4)  Print out the values in the Tree")
        print("5)  Find a node in a Binary Tree")
        print("6)  Insert a node in a Binary Tree")
        print("99) Exit")

        choice = input("Enter your choice: ")

        if choice == '1':
            tree = Tree()
            print("Binary Tree created.")

        elif choice == '2':
            if tree:
                tree.DeleteTree()
                print("Binary Tree deleted.")
            else:
                print("No Binary Tree exists yet.")

        elif choice == '3':
            if tree:
                if tree.IsEmpty():
                    print("Binary Tree is empty.")
                else:
                    print("Binary Tree is not empty.")
            else:
                print("No Binary Tree exists yet.")

        elif choice == '4':
            if tree:
                print("Tree values (in-order):")
                tree.PrintTree()
            else:
                print("No Binary Tree exists yet.")

        elif choice == '5':
            if tree:
                val = int(input("Enter the value to find: "))
                tree.find(val)
            else:
                print("No Binary Tree exists yet.")

        elif choice == '6':
            if tree:
                val = int(input("Enter the value to insert: "))
                tree.add(val)
                print(f"{val} inserted into the tree.")
            else:
                print("No Binary Tree exists yet. Please create one first.")

        elif choice == '99':
            print("Exiting...")
            break

        else:
            print("Invalid choice. Please enter a valid option.")

if __name__ == "__main__":
    menu()