@Override
    public String toString()
    {
        if (isEmpty())  return "empty";
        String result = "";
        Queue<Node> q = new Queue<>();
        q.enqueue(root);
        Node firstOnLevel = null;
        while (!q.isEmpty())
        {
            Node u = q.dequeue();
            if (u == firstOnLevel)
            {
                firstOnLevel = null;
                result += "\n";
            }
            if (u != root)  result += u.parent.key + "->";
            if (u.isRed)    result += "r";
            result += u.key + " ";
            if (u.left != null)   q.enqueue(u.left);
            if (u.right != null)   q.enqueue(u.right);
            if (firstOnLevel == null)   firstOnLevel = (u.left == null) ? u.right : u.left;
        }
        return result + "\n---";
    }