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); | |
} |
No comments:
Post a Comment