Good approach is to just simulate preorder traversal. Since we know how the sequence is built we try to consume the elements in the order they are given to use. If the next element does not fit into our contraints of lo (lower bound) and hi (upper bound) then we propagate to the parent.

As the result, running preorder on a valid sequence will consume all elements, otherwise if the sequence could not be fully consumed a non-empty sequence of the remaining elements will be returned.

This could be easily mapped to YES/NO

preorder [] lo hi = []
preorder (x:xs) lo hi = if lo < x && x < hi then rest else x:xs
    where remain = preorder xs lo x
          rest = preorder remain x hi

an option to write code in Java should be provided. solved it in java but cannot submit there as I don't know any of the languages provided.

It is nice to learn the fact that the preorder let you know the order in which the elements were inserted. I didn't reconstructed the tree though.

[SPOILER of a non optimal solution]

If the list is null then the answer is YES If it is not null I took the head, then took the tail and split it in a tuple (tail.takeWhile(x < head), tail.dropWhile(x < head)) With this you just check than all elements in tail.dropWhile(x < head) are greater than the head and check recursively the remaining two lists to see that they are BST's too.

Of course this can be optimized, I think it would be n·log n if you refine it well. This was just an idea that I tried and worked, but as mentioned in the comments this can be solved in O(n).

Really nice and fun challenge @abhiranjan !

F# solution with comment:

open System

let testBST input =
    let rec test input stack root =
        match input,stack with
        //whenever current number is smalller than root return false
        |(h::t),_ when h < root -> false
        //when top of stack is smaller then current number
        //make the top of stack the new root and pop the stack
        |(h::t),(x::s) when x < h -> test input s x 
        //if input is not empty and other states are not matched
        //push current number into stack
        |(h::t),_ -> test t (h::stack) root 
        //if all numbers a processed
        //means input is valid pre-order sequence of BST return true
        |[],_ -> true
        //if anything else happen throw an error
        |_ -> failwith "something goes wrong"
    test input [] -1

[<EntryPoint>]
let main argv =
    let num = Console.ReadLine()|>int
    let input = [
        for i in 1..num do
            //no need to know how many nodes in the tree so ignore it
            Console.ReadLine()|>ignore
            let temp = Console.ReadLine()
            yield temp.Split(" ")|>List.ofArray|>List.map(fun x -> x|>int)
    ]
    for i in input do
        if (testBST i) then printfn "%s" "YES"
        else printfn "%s" "NO"
    0 // return an integer exit code

This can actually be solved without constructing the tree (that is, building a tree structure in memory). Just need to know what state info is necessary to support the insertion rules at each point in the list. And it's O(n). :)