Algorithm


Problem Name: Data Structures - Is This a Binary Search Tree?

Problem Link: https://www.hackerrank.com/challenges/is-binary-search-tree/problem?isFullScreen=true

In this HackerRank in Data Structures - Is This a Binary Search Tree? solutions

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

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

Given the root node of a binary tree, can you determine if it's also a binary search tree?

Complete the function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must return a boolean denoting whether or not the binary tree is a binary search tree. You may have to write one or more helper functions to complete this challenge.

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

0  <= data <= 10**4

Output Format

You are not responsible for printing any output to stdout. Your function must return true if the tree is a binary search tree; otherwise, it must return false. Hidden code stubs will print this result as a Yes or No answer on a new line.

Sample Input

tree

Sample Output

No

 

 

 

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


bool checkBST(Node* root) {
        static Node *prev=NULL;
        if (root){  
        if (!checkBST(root->left))  
        return false;  
        if (prev != NULL && root->data  < = prev->data)  
        return false;  
        prev = root;  
        return checkBST(root->right);  
      }  
   return true;    
}
Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - Java Programming


 boolean checkBST(Node root) {
        return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    boolean checkBST(Node node, int min, int max){
        return node==null
            || (
            (min  <  node.data && node.data < max) 
            && checkBST(node.left, min, node.data) && checkBST(node.right,node.data, max)
        );
    }
Copy The Code & Try With Live Editor

#3 Code Example with Python Programming

Code - Python Programming


""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

""" Node is defined as
class node:
  def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
"""

def checkBST(root):
    return check_BST_subtree(root, -1, 10001)    
    
def check_binary_search_tree_(root):
    def inorder(r):
        return inorder(r.left) + [r.data] + inorder(r.right) if r else []
    
    res = inorder(root)
    return res == sorted(res) and len(set(res)) == len(res)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Swap Nodes [Algo] solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Self Balancing Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python