// region A helper class used to print BST

    /**
     * A class used to print BST.
     */
    protected static class BSTPrinter {
        public static String getString(AvlTree tree) {
            if (tree.root == null) {
                return "The tree doesn't have any nodes.";
            }

            return getString(tree.root, "", true);
        }

        private static String getString(Node node, String prefix, boolean isTail) {
            StringBuilder builder = new StringBuilder();
            String v = node.value + " (h=" + node.height + ")";

            if (node.parent != null) {
                String side = "left";
                if (node.equals(node.parent.rightChild))
                    side = "right";
                builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + side + ") " + v + "\n");
            } else {
                builder.append(prefix + (isTail ? "└── " : "├── ") + v + "\n");
            }
            java.util.List<Node> children = null;
            if (node.leftChild != null || node.rightChild != null) {
                children = new java.util.ArrayList<Node>(2);
                if (node.leftChild != null)
                    children.add(node.leftChild);
                if (node.rightChild != null)
                    children.add(node.rightChild);
            }
            if (children != null) {
                for (int i = 0; i < children.size() - 1; i++) {
                    builder.append(getString(children.get(i), prefix + (isTail ? "    " : "│   "), false));
                }
                if (children.size() >= 1) {
                    builder.append(getString(children.get(children.size() - 1), prefix + (isTail ? "    " : "│   "), true));
                }
            }

            return builder.toString();
        }
    }

    @Override
    public String toString() {
        return BSTPrinter.getString(this);
    }

    // endregion