CheckBalanced (_4_4)

CheckBalanced.java

/**
 * Check Balanced: Implement a function to check if a binary tree is balanced.
 * For the purposes of this question, a balanced tree is defined to be a tree such that
 * the heights of the two subtrees of any node never differ by more than one.
 * <p>
 * Hints : # 27, # 33 , # 49 , # 705 , # 724
 */
public class CheckBalanced {
    public static void main(String[] args) {
        Node n10 = new Node(14, null, null);

        Node n9 = new Node(13, null, null);
        Node n8 = new Node(10, null, null);
        Node n7 = new Node(12, null, n10);

        Node n6 = new Node(9, null, null);
        Node n5 = new Node(8, null, null);

        Node n4 = new Node(7, n8, n9);
        Node n3 = new Node(6, n7, null);

        Node n2 = new Node(4, n5, n6);
        Node n1 = new Node(3, n3, n4);
        Node r = new Node(0, n1, n2);

        System.out.println(solution1(r));
        System.out.println(solution2(r));
        System.out.println(solution3(r));
        System.out.println(solution4(r));
    }

    public static boolean solution1(Node root) {
        if (root == null) return true;

        System.out.print(".");
        if (getHeightSolution1(root) > 1) {
            System.out.println(root.getLeft().getValue() + " : " + root.getRight().getValue());
            return false;
        } else {
            return solution1(root.getLeft()) && solution1(root.getRight());
        }
    }

    public static int getHeightSolution1(Node root) {
        if (root.getLeft() == null || root.getRight() == null) return -1;
        return Math.abs(root.getLeft().getValue() - root.getRight().getValue());
    }

    public static boolean solution2(Node root) {
        if (root == null) return true;

        int heightDiff = getHeightSolution2(root.getLeft()) - getHeightSolution2(root.getRight());

        System.out.print(".");
        if (Math.abs(heightDiff) > 1) {
            return false;
        } else {
            return solution2(root.getLeft()) && solution2(root.getRight());
        }
    }

    public static int getHeightSolution2(Node root) {
        if (root == null) return -1;
        return Math.max(getHeightSolution2(root.getLeft()), getHeightSolution2(root.getRight()) + 1);
    }

    public static boolean solution3(Node root) {
        return checkHeight(root.getLeft()) != Integer.MIN_VALUE;
    }

    public static int checkHeight(Node root) {
        if (root == null) return -1;
        System.out.print(".");

        int leftHeight = checkHeight(root.getLeft());
        if (leftHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE;

        int rightHeight = checkHeight(root.getRight());
        if (rightHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE;

        int heightDiff = leftHeight - rightHeight;

        if (Math.abs(heightDiff) > 1) {
            return Integer.MIN_VALUE;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    public static boolean solution4(Node n) {
        return solution4(n, null, null);
    }

    public static boolean solution4(Node n, Integer min, Integer max) {
        if (n == null) {
            return true;
        }
        System.out.print(".");

        if ((min != null && n.getValue() <= min) || (max != null && n.getValue() > max)) {
            return false;
        }

        if (!solution4(n.getLeft(), min, n.getValue()) || !solution4(n.getRight(), max, n.getValue())) {
            return false;
        }

        return true;
    }

}

class Node {
    private int value;
    private Node left;
    private Node right;

    public Node() {
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value + " ";
    }
}