Company: Meesho
Difficulty: medium
Binary Search Tree Validation A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value (its node number in this case). A tree may either be: An empty tree, the root is null A non-empty tree with a non-null root node that contains a value and up to 2 subtrees, left and right , which are also binary trees A binary tree is classified as a binary search tree (BST) if all of the non-null nodes exhibit two properties: The left subtree of each node contains only nodes with values that are lower than its own value The right subtree of each node contains only nodes with values that are higher than its own value A pre-order traversal is a recursive tree traversal method where the current node is visited first, then the left subtree, and then the right subtree. Input Format The following parameters are read from stdin: The first line contains an integer q, the number of queries The next q sets of lines are defined as: The first line cont