package com.janosgyerik.utils.algorithm.tree.binarytree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public final class TreeUtils {

    private TreeUtils() {
        throw new AssertionError("utility class, forbidden constructor");
    }

    /**
     * "Pretty print" a tree, something like this:
     *                    A
     *          B                  C
     *     D        E         F         G
     *  H    I    J    K    L    M    N    O
     * P Q  R S  T U  V W  X Y  Z 1  2 3  4 5
     *
     * @param root The root node of the tree
     */
    public static void print(TreeNode<?> root) {
        if (root == null) {
            return;
        }

        int height = height(root);

        Queue<TreeNode<?>> queue = new LinkedList<>();
        queue.add(root);

        for (int level = 1; level <= height; ++level) {
            int paddingFirst = (int) Math.pow(2, (double) height - level);
            int paddingBetween = paddingFirst * 2 - 1;

            printPadding(paddingFirst);

            List<TreeNode<?>> copy = new LinkedList<>(queue);
            queue.clear();

            for (TreeNode<?> node : copy) {
                if (node == null) {
                    System.out.print(" ");
                    queue.add(null);
                    queue.add(null);
                } else {
                    System.out.print(node.value);
                    queue.add(node.left);
                    queue.add(node.right);
                }
                printPadding(paddingBetween);
            }
            System.out.println();
        }
    }

    private static void printPadding(int padding) {
        for (int i = 0; i < padding; ++i) {
            System.out.print(" ");
        }
    }

    public static int height(TreeNode<?> root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public static int size(TreeNode<?> root) {
        if (root == null) {
            return 0;
        }
        return 1 + size(root.left) + size(root.right);
    }

    static <T extends Comparable<T>> boolean isBinarySearchTree(TreeNode<T> root, T minValue, T maxValue) {
        if (root == null) {
            return true;
        }
        return less(minValue, root.value)
            && less(root.value, maxValue)
            && isBinarySearchTree(root.left, minValue, root.value)
            && isBinarySearchTree(root.right, root.value, maxValue);
    }

    private static <T extends Comparable<T>> boolean less(T left, T right) {
        return left.compareTo(right) < 0;
    }
}

@@ -51,16 +51,44 @@
 ytree;%0A%0A
+import java.io.PrintStream;%0A
 import j
@@ -649,32 +649,49 @@
 TreeNode%3C?%3E root
+, PrintStream out
 ) %7B%0A        if (
@@ -1062,24 +1062,29 @@
 rintPadding(
+out, 
 paddingFirst
@@ -1269,39 +1269,32 @@
                 
-System.
 out.print(%22 %22);%0A
@@ -1404,39 +1404,32 @@
                 
-System.
 out.print(node.v
@@ -1567,16 +1567,21 @@
 Padding(
+out, 
 paddingB
@@ -1607,39 +1607,32 @@
   %7D%0A            
-System.
 out.println();%0A 
@@ -1684,16 +1684,33 @@
 Padding(
+PrintStream out, 
 int padd
@@ -1776,15 +1776,8 @@
     
-System.
 out.

Make PrintStream a parameter