Validate Binary Search Tree

Table of Contents

Problem

In Validate Binary Search Tree problem we have given the root of a tree, we have to check if it is a binary search tree or not.

Example :

Output:

true

Explanation: The given tree is a binary search tree because all elements which are left to each subtree are smaller than the root of the subtree. All elements that are right to each subtree are greater than the root of the subtree and each subtree is itself a binary search tree.

Approach

First, we do inorder traversal of the given tree and store it in an array. Then we check if the array is sorted in increasing order. Then we say it is a binary search tree else it is not a binary search tree.
To minimize the use of auxiliary space we can keep track of previously visited node and if the current node is smaller than the previous node then it is not a binary search tree and if all the previous nodes are smaller than the current node then it a binary search tree.
We can avoid the use of extra space by passing the previous node as a parameter.

C++ code For Validate Binary Search Tree

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
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; 
  
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 


bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root) 
  { 
    if (!isBSTUtil(root->left, prev)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data) 
    return false; 

    prev = root; 

    return isBSTUtil(root->right, prev); 
  } 

  return true; 
} 

bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

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

  if (isBST(root)) 
    cout << "Is BST"; 
  else
    cout << "Not a BST"; 

  return 0; 
}

Java code For Validate Binary Search Tree

// Java program to check if a given tree is BST. 
class Check
{ 
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node 
{ 
  int data; 
  Node left, right; 
  
  Node(int data) 
  { 
    this.data = data; 
    left = right = null; 
  } 
}; 
static Node prev; 

static boolean isBSTUtil(Node root) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root != null) 
  { 
    if (!isBSTUtil(root.left)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != null && root.data <= prev.data) 
    return false; 

    prev = root; 

    return isBSTUtil(root.right); 
  } 
  return true; 
} 

static boolean isBST(Node root) 
{ 
  return isBSTUtil(root); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
  Node root = new Node(3); 
  root.left	 = new Node(2); 
  root.right	 = new Node(5); 
  root.left.left = new Node(1); 
  root.left.right = new Node(4); 

  if (isBST(root)) 
    System.out.print("Is BST"); 
  else
    System.out.print("Not a BST"); 
} 
}

Not a BST

Time complexity

O(n) as we are traversing each node only once.

Space complexity

O(n) because we are storing each traversed node and check if the array is sorted in increasing order to check if the tree is Binary Search Tree or not.

References