//LEVELORDER
void levelorder() const {
        queue<Node*> que;
        que.push(root);

        while(!que.empty()) {
            Node* current = que.front();
            que.pop();
            if (current) {
                cout << current->data << " ";

                if (current->left) {
                    que.push(current->left);
                }
                if (current->right) {
                    que.push(current->right);
                }
            }
        }
    }

//REMOVE ITEM
Node* _remove(int value, Node* current) {
        if (!current) {
            return nullptr;
        }

        if (value < current->data) {
            current->left = _remove(value, current->left);
        } else if (value > current->data) {
            current->right = _remove(value, current->right);
        } else { // value = current->data;
            if (!current->left && !current->right) {
                free(current);
                return nullptr;
            } else if (!current->left) {
                Node* tempRight = current->right;
                free(current);
                return tempRight;
            } else if (!current->right) {
                Node* tempLeft = current->left;
                free(current);
                return tempLeft;
            } else {
                Node* swapWith = current->right;
                while (swapWith->left) {
                    swapWith = swapWith->left;
                }

                current->data = swapWith->data;
                current->right = _remove(swapWith->data, current->right);
            }
        }

        current->calculateHeight();
        current->fixTree();

        return current;
    }

// Function to print Nodes in a binary tree in Level order
void LevelOrder(Node* root)  //DLR (Data-Left-Right)
{
	if (root == nullptr) return;
	std::queue<Node*> Q;
	Q.push(root);
	while (!Q.empty())
	{
		Node* current = Q.front();
		Q.pop(); // removing the element at front
		std::cout << current->data << " ";
		if (current->left != nullptr) Q.push(current->left);
		if (current->right != nullptr) Q.push(current->right);
	}
}

// Function to print Nodes in a binary tree in Level order
void LevelOrder(Node* root)  //DLR (Data-Left-Right)
{
	if (root == nullptr) return;
	std::queue<Node*> Q;
	Q.push(root);
	Q.push(nullptr); // whenever a level is over we will insert nullptr
	//while there is at least one discovered node
	while (!Q.empty())
	{
		Node* current = Q.front();

		if (current == nullptr)
		{
			Q.pop(); // removing the element at front
			Q.push(nullptr); // takes care of the next level
			if (Q.front()==nullptr)
			{
				return; // if there are two consecutive nullptr in the queue
			}
			std::cout << '\n';
		}
		else
		{
			if (current->left != nullptr) Q.push(current->left);
			if (current->right != nullptr) Q.push(current->right);
			std::cout << current->data << " ";
			Q.pop();
		}

	}
}