We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
openSystemlettestBSTinput=letrectestinputstackroot=matchinput,stackwith//whenever current number is smalller than root return false|(h::t),_whenh<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)whenx<h->testinputsx//if input is not empty and other states are not matched//push current number into stack|(h::t),_->testt(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"testinput[]-1[<EntryPoint>]letmainargv=letnum=Console.ReadLine()|>intletinput=[foriin1..numdo//no need to know how many nodes in the tree so ignore itConsole.ReadLine()|>ignorelettemp=Console.ReadLine()yieldtemp.Split(" ")|>List.ofArray|>List.map(funx->x|>int)]foriininputdoif(testBSTi)thenprintfn"%s""YES"elseprintfn"%s""NO"0// return an integer exit code
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.
Could someone pls point us to a javascript or python solution?....
F# solution with comment:
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
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.
python, java or cpp are not in the list :(