Construct-Binary-Search-Tree-From-Preorder-Traversal.scala

classTreeNode(_value: Int=0, _left: TreeNode=null, _right: TreeNode=null) {
varvalue:Int= _value
varleft:TreeNode= _left
varright:TreeNode= _right
}

//DFS solution
objectSolution {
defbstFromPreorder(preorder: Array[Int]):TreeNode= {
varparentList= scala.collection.mutable.Seq.empty[TreeNode]
valroot=newTreeNode(preorder(0))

defbstFromPreorderWithIndex(index: Int, parent: TreeNode):Unit= {
if (index != preorder.length) {
if (parent.value > preorder(index)) {
 parent.left =newTreeNode(preorder(index))
 parentList = parentList.+:(parent)
 bstFromPreorderWithIndex(index +1, parent.left)
 } else {
if (parentList.isEmpty || preorder(index) < parentList.head.value) {
 parent.right =newTreeNode(preorder(index))
 bstFromPreorderWithIndex(index +1, parent.right)
 } else {
valnewParent= parentList.head
 parentList = parentList.tail
 bstFromPreorderWithIndex(index, newParent)
 }
 }
 }
 }

 bstFromPreorderWithIndex(1, root)
 root
 }
}

//recursive (not tailRec) solution
objectSolution2 {
defbstFromPreorder(preorder: Array[Int]):TreeNode=
 bstFromPreorderWithRange(0, preorder.length -1, preorder)

defbstFromPreorderWithRange(start: Int, end: Int, preorder: Array[Int]):TreeNode= {
if (start > end) null
else {
valnode=newTreeNode(preorder(start))
valleftIndexBound= (start to end).find(i => preorder(i) > preorder(start)).getOrElse(end +1) -1
 node.left = bstFromPreorderWithRange(start +1, leftIndexBound, preorder)
 node.right = bstFromPreorderWithRange(leftIndexBound +1, end, preorder)
 node
 }
 }
}