validate binary search tree code example
Example 1: check if binary search tree is valid
class BTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
/**
*
* @param {BTNode} tree
* @returns {Boolean}
*/
const isBinarySearchTree = (tree) => {
if (tree) {
if (
tree.left &&
(tree.left.value > tree.value || !isBinarySearchTree(tree.left))
) {
return false;
}
if (
tree.right &&
(tree.right.value <= tree.value || !isBinarySearchTree(tree.right))
) {
return false;
}
}
return true;
};
Example 2: check for bst
// C++ program to check if a given tree is BST.
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node
{
int data;
struct Node* left, *right;
};
// Returns true if given tree is BST.
bool isBST(Node* root, Node* l=NULL, Node* r=NULL)
{
// Base condition
if (root == NULL)
return true;
// if left node exist then check it has
// correct data or not i.e. left node's data
// should be less than root's data
if (l != NULL and root->data <= l->data)
return false;
// if right node exist then check it has
// correct data or not i.e. right node's data
// should be greater than root's data
if (r != NULL and root->data >= r->data)
return false;
// check recursively for every node.
return isBST(root->left, l, root) and
isBST(root->right, root, r);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
struct Node *root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
if (isBST(root,NULL,NULL))
cout << "Is BST";
else
cout << "Not a BST";
return 0;
}
Example 3: binary tree search
/* This is just the seaching function you need to write the required code.
Thank you. */
void searchNode(Node *root, int data)
{
if(root == NULL)
{
cout << "Tree is empty\n";
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node *temp = q.front();
q.pop();
if(temp->data == data)
{
cout << "Node found\n";
return;
}
if(temp->left != NULL)
q.push(temp->left);
if(temp->right != NULL)
q.push(temp->right);
}
cout << "Node not found\n";
}
Example 4: binary search tree
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in array")