Validate Binary Search Tree (BST)

You are given a binary tree with 'N' integer nodes. Your task is to determine whether this binary tree is a Binary Search Tree (BST).

BST Definition:

A Binary Search Tree (BST) is a binary tree where each node has the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Example:

Answer:

Level 1: 

All the nodes in the left subtree of 4 (2, 1, 3) are smaller 
than 4, all the nodes in the right subtree of the 4 (5) are 
larger than 4.

Level 2 :

For node 2: 
All the nodes in the left subtree of 2 (1) are smaller than 
2, all the nodes in the right subtree of the 2 (3) are larger than 2. 
For node 5:
The left and right subtrees for node 5 are empty.

Level 3: 

For node 1:
The left and right subtrees for node 1 are empty. 
For node 3: 
The left and right subtrees for node 3 are empty.

Because all the nodes follow the property of a binary search tree, the above tree is a binary search tree.

Input:

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of input contains the elements of the tree in the level order form separated by a single space.

If any node does not have a left or right child, take -1 in its place. Refer to the example below.

Example :

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Output:

For each test case, print ‘true’ if the binary tree is a BST, else print ‘false’.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• -10^6 <= data <= 10^6 and data != -1

where N is the number of nodes in the tree, T represents the number of test cases, and ‘data’ denotes data contained in the node of the binary tree.

Note:

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.