Trees: Is This a Binary Search Tree? HackerRank Solution

Trees: Is This a Binary Search Tree? HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-is-binary-search-tree

For the purposes of this challenge, we define a binary search tree to be a binary tree with the following properties:

• The value of every node in a node's left subtree is less than the data value of that node.
• The value of every node in a node's right subtree is greater than the data value of that node.
• The value of every node is distinct.

For example, the image on the left below is a valid BST. The one on the right fails on several counts:
- All of the numbers on the right branch from the root are not larger than the root.
- All of the numbers on the right branch from node 5 are not larger than 5.
- All of the numbers on the left branch from node 5 are not smaller than 5.
- The data value 1 is repeated.

Given the root node of a binary tree, determine if it is a binary search tree.

Function Description

Complete the function checkBST in the editor below. It must return a boolean denoting whether or not the binary tree is a binary search tree.

checkBST has the following parameter(s):

• root: a reference to the root node of a tree to test

Input Format

You are not responsible for reading any input from stdin. Hidden code stubs will assemble a binary tree and pass its root node to your function as an argument.

Constraints

Output Format

Your function must return a boolean true if the tree is a binary search tree. Otherwise, it must return false.

Sample Input

Sample Output

Yes

Explanation

The tree in the diagram satisfies the ordering property for a Binary Search Tree, so we print Yes.

Source : https://www.hackerrank.com/challenges/ctci-is-binary-search-tree

Solution

	// Karthikalapati.blogspot.com
	/*
	The Node class is defined as follows:
	class Node {
	int data;
	Node left;
	Node right;
	}
	*/
	boolean checkBST(Node root) {
	return checkBST(root, 0, 10000); // range of values in problem
	}
	boolean checkBST(Node node, int min, int max) {
	if (node == null) {
	return true;
	} else if (node.data < min || node.data > max) {
	return false;
	}
	return checkBST(node.left, min, node.data - 1) && checkBST(node.right, node.data + 1, max);
	}