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, (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);
    }

    public static <T extends Comparable<T>> boolean isBinarySearchTree(TreeNode<T> root, T minValue, T maxValue) {
        return root == null ||
                minValue.compareTo(root.value) < 0 && root.value.compareTo(maxValue) < 0
                && isBinarySearchTree(root.left, minValue, root.value)
                && isBinarySearchTree(root.right, root.value, maxValue);
    }
}

@@ -328,16 +328,20 @@
 this:%0A  
+   *
         
@@ -353,24 +353,27 @@
        A%0A   
+  *
           B 
@@ -396,19 +396,22 @@
  C%0A     
+*
    
+  
 D       
@@ -436,16 +436,19 @@
    G%0A   
+  *
   H    I
@@ -481,16 +481,19 @@
    O%0A   
+  *
  P Q  R 
@@ -915,16 +915,24 @@
 pow(2, (
+double) 
 height -
@@ -938,17 +938,16 @@
 - level)
-)
 ;%0A      
@@ -2114,31 +2114,24 @@
 %0A    %7D%0A%0A    
-public 
 static %3CT ex
@@ -2230,23 +2230,20 @@
         
-return 
+if (
 root == 
@@ -2250,11 +2250,36 @@
 null
- %7C%7C
+) %7B%0A            return true;
 %0A   
@@ -2283,24 +2283,26 @@
         
+%7D%0A
         
 minValue
@@ -2297,85 +2297,84 @@
     
-minValue.compareTo(root.value) %3C 0 && root.value.compareTo(maxValue) %3C 0%0A    
+return less(minValue, root.value)%0A            && less(root.value, maxValue)%0A
     
@@ -2440,36 +2440,32 @@
 ue)%0A            
-    
 && isBinarySearc
@@ -2510,11 +2510,137 @@
 );%0A    %7D
+%0A%0A    private static %3CT extends Comparable%3CT%3E%3E boolean less(T left, T right) %7B%0A        return left.compareTo(right) %3C 0;%0A    %7D
 %0A%7D%0A

Split complex condition