A binary search tree contains the values-$1,2,3,4,5,6,7$ and $8.$ The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output?
- $5\;\;3\;\;1\;\;2\;\;4\;\;7\;\;8\;\;6\;\;$
- $5\;\;3\;\;1\;\;2\;\;6\;\;4\;\;9\;\;7$
- $5\;\;3\;\;2\;\;4\;\;1\;\;6\;\;7\;\;8$
- $5\;\;3\;\;1\;\;2\;\;4\;\;7\;\;6\;\;8$