Question

PLEASE READ CAREFULY AND EXPLAIN YOUR WORK:

(JavaScript) only

Search the Tree:

A binary search tree is a data structure that consists of JavaScript objects called "nodes". A tree always has a root node which holds its own integer value property and can have up to two child nodes (or leaf nodes), a left and right property. A leaf node holds a value attribute and, likewise, a left and right attribute each potentially pointing to another node in the binary tree. Think of it as a javascript object with potentially more sub-objects referenced by the left and right attributes (as seen in assignment 4). There are certain rules that apply to a binary tree:

• A node's left leaf node has a value that is <= than to its own value
• A node's right leaf node has a value that is => its own value

In other words:

let node = {
  value: <some number>
  left: <a node object with value attribute <= this object's value>
  right: <a node object with value attribute >= this object's value>
}

If you need a visual aid, below is an example of what a binary tree looks like according to the above rules:

You will be writing a function called isPresent that takes two arguments: the root object and a value (number), and returns a boolean true if the value is present in the tree or false if it is not present.

function isPresent(root, value) {
    // your code here
    // return boolean
}

Example test case:

Inputs: 
root => { 
  "value": 5, 
  "left": {
    "value": 3,
    "left": {
      "value": 2,
      "left": null,
      "right": null
    },
    "right": {
      "value": 4,
      "left": null,
      "right": null
    }
  }, 
  "right": {
    "value": 7,
    "left": {
      "value": 6,
      "left": null,
      "right": null
    },
    "right": {
      "value": 8,
      "left": null,
      "right": null
    }
  }
}
value => 6

Output: true
Reasoning: 6 is the value of a leaf node in the binary tree
..
"left": {
  "value": 6,
  "left": null,
  "right": null
},
..

Answer 1

A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.

METHOD 1 (Simple but Wrong)
Following is a simple program. For each node, check if the left node of it is smaller than the node and right node of it is greater than the node.

int isBST(struct node* node)
{
if (node == NULL)
   return 1;
  
/* false if left is > than node */
if (node->left != NULL && node->left->data > node->data)
   return 0;
  
/* false if right is < than node */
if (node->right != NULL && node->right->data < node->data)
   return 0;
  
/* false if, recursively, the left or right is not a BST */
if (!isBST(node->left) || !isBST(node->right))
   return 0;
  
/* passing all that, it's a BST */
return 1;
}

This approach is wrong as this will return true for below binary tree (and below tree is not a BST because 4 is in left subtree of 3)

METHOD 2 (Correct but not efficient)
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
if (node == NULL)
   return 1;
  
/* false if the max of the left is > than us */
if (node->left!=NULL && maxValue(node->left) > node->data)
   return 0;
  
/* false if the min of the right is <= than us */
if (node->right!=NULL && minValue(node->right) < node->data)
   return 0;
  
/* false if, recursively, the left or right is not a BST */
if (!isBST(node->left) || !isBST(node->right))
   return 0;
  
/* passing all that, it's a BST */
return 1;
}

It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree

METHOD 3 (Correct and Efficient):
Method 2 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.

Below is the implementation of the above approach:

C++

#include<bits/stdc++.h>

using namespace std;

/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class node
{
   public:
   int data;
   node* left;
   node* right;
  
   /* Constructor that allocates
   a new node with the given data
   and NULL left and right pointers. */
   node(int data)
   {
       this->data = data;
       this->left = NULL;
       this->right = NULL;
   }
};

int isBSTUtil(node* node, int min, int max);

/* Returns true if the given
tree is a binary search tree
(efficient version). */
int isBST(node* node)
{
   return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given
tree is a BST and its values
are >= min and <= max. */
int isBSTUtil(node* node, int min, int max)
{
   /* an empty tree is BST */
   if (node==NULL)
       return 1;
          
   /* false if this node violates
   the min/max constraint */
   if (node->data < min || node->data > max)
       return 0;
  
   /* otherwise check the subtrees recursively,
   tightening the min or max constraint */
   return
       isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
       isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}

/* Driver code*/
int main()
{
   node *root = new node(4);
   root->left = new node(2);
   root->right = new node(5);
   root->left->left = new node(1);
   root->left->right = new node(3);
  
   if(isBST(root))
       cout<<"Is BST";
   else
       cout<<"Not a BST";
      
   return 0;
}

// This code is contributed by rathbhupendra

C procramming code

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
   int data;
   struct node* left;
   struct node* right;
};

int isBSTUtil(struct node* node, int min, int max);

/* Returns true if the given tree is a binary search tree
(efficient version). */
int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its
values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max)
{
/* an empty tree is BST */
if (node==NULL)
   return 1;
      
/* false if this node violates the min/max constraint */
if (node->data < min || node->data > max)
   return 0;

/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
   isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
   isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}

/* 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 = (struct node*)
                   malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(4);
root->left   = newNode(2);
root->right   = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);

if(isBST(root))
   printf("Is BST");
else
   printf("Not a BST");
  
getchar();
return 0;
}

Java programming Code

//Java implementation to check if given Binary tree
//is a BST or not

/* Class containing left and right child of current
node and key value*/
class Node
{
   int data;
   Node left, right;

   public Node(int item)
   {
       data = item;
       left = right = null;
   }
}

public class BinaryTree
{
   //Root of the Binary Tree
   Node root;

   /* can give min and max value according to your code or
   can write a function to find min and max value of tree. */

   /* returns true if given search tree is binary
   search tree (efficient version) */
   boolean isBST() {
       return isBSTUtil(root, Integer.MIN_VALUE,
                           Integer.MAX_VALUE);
   }

   /* Returns true if the given tree is a BST and its
   values are >= min and <= max. */
   boolean isBSTUtil(Node node, int min, int max)
   {
       /* an empty tree is BST */
       if (node == null)
           return true;

       /* false if this node violates the min/max constraints */
       if (node.data < min || node.data > max)
           return false;

       /* otherwise check the subtrees recursively
       tightening the min/max constraints */
       // Allow only distinct values
       return (isBSTUtil(node.left, min, node.data-1) &&
               isBSTUtil(node.right, node.data+1, max));
   }

   /* Driver program to test above functions */
   public static void main(String args[])
   {
       BinaryTree tree = new BinaryTree();
       tree.root = new Node(4);
       tree.root.left = new Node(2);
       tree.root.right = new Node(5);
       tree.root.left.left = new Node(1);
       tree.root.left.right = new Node(3);

       if (tree.isBST())
           System.out.println("IS BST");
       else
           System.out.println("Not a BST");
   }
}

Python Programming Code

# Python program to check if a binary tree is bst or not

INT_MAX = 4294967296
INT_MIN = -4294967296

# A binary tree node
class Node:

   # Constructor to create a new node
   def __init__(self, data):
       self.data = data
       self.left = None
       self.right = None

# Returns true if the given tree is a binary search tree
# (efficient version)
def isBST(node):
   return (isBSTUtil(node, INT_MIN, INT_MAX))

# Retusn true if the given tree is a BST and its values
# >= min and <= max
def isBSTUtil(node, mini, maxi):
  
   # An empty tree is BST
   if node is None:
       return True

   # False if this node violates min/max constraint
   if node.data < mini or node.data > maxi:
       return False

   # Otherwise check the subtrees recursively
   # tightening the min or max constraint
   return (isBSTUtil(node.left, mini, node.data -1) and
       isBSTUtil(node.right, node.data+1, maxi))

# Driver program to test above function
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)

if (isBST(root)):
   print "Is BST"
else:
   print "Not a BST"

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Output:

IS BST

Time Complexity: O(n)
Auxiliary Space : O(1) if Function Call Stack size is not considered, otherwise O(n)