Problem Statement

Binary Search Tree Validation A binary tree is a branching structure in which each node stores one value and links to at most two children. Such a tree is defined recursively as either: An empty tree, whose root is null A non-empty tree, whose root holds a value together with two further binary trees called its left and right subtrees A binary tree qualifies as a binary search tree (BST) exactly when every non-null node in it satisfies both of the following: every value in that node's left subtree is strictly smaller than its own value every value in that node's right subtree is strictly larger than its own value A pre-order walk visits a node itself first, then recurses into its left subtree, then its right subtree. Input Format Read the following from stdin: The first line holds an integer q, the number of test cases Each of the q test cases consists of: A line with an integer n, the number of nodes in that test case's tree A line with a[n]: n space-separated integers giving the sequ