Check the Structure

Problem Statement

Check the Structure Problem Description You are given a sequence of integers that is claimed to be the pre-order traversal of a binary tree. Decide whether some binary tree with that exact pre-order traversal can be a Binary Search Tree (BST) . A binary tree is made of nodes; each node holds a value and has at most two children, a left child and a right child. A tree is a BST when, for every node: the left subtree of that node contains only values strictly less than the node's value, and the right subtree of that node contains only values strictly greater than the node's value. A pre-order traversal visits the root first, then the whole left subtree, then the whole right subtree: preorder(node): if node is empty: return the empty list return [node.value] + preorder(node.left) + preorder(node.right) For each given sequence, print YES if at least one BST has exactly that pre-order traversal, and NO otherwise. Input Format The first line contains a single integer q - the number of queries