ValidateBST (_4_5)

ValidateBST.java

/**
 * Validate BST: Implement a function to check if a binary tree is a binary search tree.
 * Hints: #35, #57, #86, # 773, # 728
 */
public class ValidateBST {
    public static void main(String[] args) {
        Node n6 = new Node(25, null, null);
        Node n5 = new Node(13, null, null);

        Node n4 = new Node(8, null, null);
        Node n3 = new Node(3, null, null);

        Node n2 = new Node(20, n5, n6);
        Node n1 = new Node(5, n3, n4);
        Node r = new Node(10, n1, n2);

        System.out.println(solution1(r));

        n3.setValue(6);
        System.out.println(solution1(r));

        n3.setValue(3);
        Node n7 = new Node(22, null, null);
        n6.setLeft(n7);
        System.out.println(solution1(r));
    }

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

        int parentValue = root.getValue();

        int leftValue;
        if (root.getLeft() != null) {
            leftValue = root.getLeft().getValue();
        } else {leftValue = parentValue;}

        int rightValue;
        if (root.getRight() != null) {
            rightValue = root.getRight().getValue();
        } else {rightValue = parentValue;}

        if (leftValue > parentValue || rightValue < parentValue) {
            return false;
        }

        System.out.print(".");
        return solution1(root.getLeft()) && solution1(root.getRight());
    }
}

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 + " ";
    }
}