title: Checking if given preorder traversal is valid BST
body: <p>I was writing code to check from preorder traversal if it is a valid BST. 
  e.g preorder traversal <code>1,2,4,3,5</code>  is valid BST while <code>1,3,4,2</code> is not</p>
  
  <p>I built whole tree from that preorder sequence and then checked if that tree is a valid BST. This is <code>O(N)</code> solutions with respect to both space and time complexity.</p>
  
  <p>Does anybody have good approach than this? I have intuition that we can do this in O(1) extra space.</p>