Heads up, guys. Before Solving please read


#1

The sample example given is wrong.
Expected time complexity O(n)
Try to mimic preorder traversal using stack and find at what condition pre-order traversal will not be valid.
Hope It helps.