Given a binary tree, write a program to check if it is a valid Binary Search Tree(BST).

Problem Note

A BST 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 BST.
  • Return 1 if the given binary tree is a BST, else return 0.

Example 1

      5
     /  \
    3    6
   / \   
  2   4 
 /
1
Input: [5, 3, 6, 2, 4, -1, -1, 1, -1, -1, -1, -1, -1]
Output: 1
Explanation: Every node satisties the properties of a BST. 

Example 2

   10
   / \
  5   4
Input: [10, 5, 4]
Output: 0
Explanation: The root node's value is 10 but its right child's value is 4.