Is This a Binary Search Tree? Hackerrank problem solution

Is This a Binary Search Tree? Hackerrank

For the purposes of this challenge, we define a binary search tree to be a binary 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 <= 104
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

Is This a Binary Search Tree? Hackerrank

Sample Output

No

Solution
/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.  

The Node struct is defined as follows:
	struct Node {
		int data;
		Node* left;
		Node* right;
	}
*/
bool check(Node* root, int maxLeft, int minRight) {
    if(!root) return true;
    if(root->data <= maxLeft || root->data >= minRight) return false;
    return check(root->left, maxLeft, root->data) && check(root->right, root->data, minRight);
}

bool checkBST(Node* root) { return check(root, -1, 10001); }
boolean checkBST(Node root, int minValue, int maxValue) {
    if (root == null) {
        return true;
    }
    
    if (root.data < minValue || root.data > maxValue) {
        return false;
    }
    
    return (    checkBST(root.left, minValue, root.data - 1) 
            &&  checkBST(root.right, root.data + 1, maxValue)
            );
}
    
boolean checkBST(Node root) {
    return checkBST(root, 0, 10000);
}
C++
bool checkBST(Node* root, int minValue, int maxValue) {
    if (root == NULL) {
        return true;
    }

    if (root->data < minValue || root->data > maxValue) {
        return false;
    }

    return (    checkBST(root->left, minValue, root->data - 1) 
            &&  checkBST(root->right, root->data + 1, maxValue)
            );
}

bool checkBST(Node* root) {
    return checkBST(root, 0, 10000);
}

 

 

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.