Is This a Binary Search Tree? (Java)

Write a function that takes a binary tree and returns true if it is a binary search tree, and false if not.

In our test code, we're going to use the following examples:

head1 = 0
       / \
      1   2
     /\   /\
    3  4 5  6

head1 is NOT a binary search tree.

head2 = 3
      /   \
     1     4
    /\    / \
   0  2  5   6

head2 is NOT a binary search tree.

head3 = 3
      /   \
     1     5
    /\    / \
   0  2  4   6

head3 is a binary search tree.

head4 = 3
      /   \
     1     5
    /\
   0  4

head4 is NOT a binary search tree.

풀이

Hacker Rank에서도 같은 문제를 풀었는데 모르고 블로그에 올리지 않았었다.

여기에서도 나온거보면 꽤나 단골?문제로 보여지니 알아두는게 좋을 듯!

중요포인트는 left로 갈 때는 left의 value가 이전 head의 value보다는 작아야 한다(크거나 같으면 false)

반대로 right로 갈 때는 right의 value가 이전 head value보다 커야 한다(작거나 같으면 false)

이부분만 명심하면 그리 어렵지 않은 문제이다.

package com.company;

import java.util.HashMap;

public class Main {

    public static void main(String[] args) {
        // NOTE: The following input values will be used for testing your solution.
        // The mapping we're going to use for constructing a tree.
        // For example, {0: [1, 2]} means that 0's left child is 1, and its right
        // child is 2.
        HashMap<Integer, int[]> mapping1 = new HashMap<Integer, int[]>();
        int[] childrenA = {1, 2};
        int[] childrenB = {3, 4};
        int[] childrenC = {5, 6};
        mapping1.put(0, childrenA);
        mapping1.put(1, childrenB);
        mapping1.put(2, childrenC);

        TreeNode head1 = createTree(mapping1, 0);
        // This tree is:
        // head1 = 0
        //        / \
        //       1   2
        //      /\   /\
        //     3  4 5  6


        HashMap<Integer, int[]> mapping2 = new HashMap<Integer, int[]>();
        int[] childrenD = {1, 4};
        int[] childrenE = {0, 2};
        int[] childrenF = {5, 6};
        mapping2.put(3, childrenD);
        mapping2.put(1, childrenE);
        mapping2.put(4, childrenF);

        TreeNode head2 = createTree(mapping2, 3);
        // This tree is:
        //  head2 = 3
        //        /   \
        //       1     4
        //      /\    / \
        //     0  2  5   6


        HashMap<Integer, int[]> mapping3 = new HashMap<Integer, int[]>();
        int[] childrenG = {1, 5};
        int[] childrenH = {0, 2};
        int[] childrenI = {4, 6};
        mapping3.put(3, childrenG);
        mapping3.put(1, childrenH);
        mapping3.put(5, childrenI);

        TreeNode head3 = createTree(mapping3, 3);
        // This tree is:
        //  head3 = 3
        //        /   \
        //       1     5
        //      /\    / \
        //     0  2  4   6


        HashMap<Integer, int[]> mapping4 = new HashMap<Integer, int[]>();
        int[] childrenJ = {1, 5};
        int[] childrenK = {0, 4};
        mapping4.put(3, childrenJ);
        mapping4.put(1, childrenK);

        TreeNode head4 = createTree(mapping4, 3);
        // This tree is:
        //  head4 = 3
        //        /   \
        //       1     5
        //      /\
        //     0  4


        // isBST(head1) should return false
        // isBST(head2) should return false
         System.out.println(isBST(head3));
//         should return true
        // isBST(head4) should return false
    }


    // Implement your function below.
    public static boolean isBST(TreeNode node) {
        return isBST(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public static boolean isBST(TreeNode node, int lowest, int highest){
        if (node == null) return true;
        if (node.value <= lowest || node.value >= highest) return false;
        return isBST(node.left, lowest, node.value) && isBST(node.right, node.value, highest);
    }


    // A function for creating a tree.
    // Input:
    // - mapping: a node-to-node mapping that shows how the tree should be constructed
    // - headValue: the value that will be used for the head node
    // Output:
    // - The head node of the resulting tree
    public static TreeNode createTree(HashMap<Integer, int[]> mapping, int headValue) {
        TreeNode head = new TreeNode(headValue, null, null);
        HashMap<Integer, TreeNode> nodes = new HashMap<>();
        nodes.put(headValue, head);
        for (Integer key : mapping.keySet()) {
            int[] value = mapping.get(key);
            TreeNode leftChild = new TreeNode(value[0], null, null);
            TreeNode rightChild = new TreeNode(value[1], null, null);
            nodes.put(value[0], leftChild);
            nodes.put(value[1], rightChild);
        }
        for (Integer key : mapping.keySet()) {
            int[] value = mapping.get(key);
            nodes.get(key).left = nodes.get(value[0]);
            nodes.get(key).right = nodes.get(value[1]);
        }
        return head;
    }
}