case class TreeNode(left: Option[TreeNode], value: Int, right: Option[TreeNode])

object TreeNode {
  def empty: TreeNode = TreeNode(None, 0, None)
}

case class Tree(rootNode: TreeNode) {
  def add(valToAdd: Int): Tree = {
    def addRec(recValToAdd: Int, recCurrNode: TreeNode): TreeNode = {
      recCurrNode match {
        case TreeNode(None, 0, None) => TreeNode(None, recValToAdd, None)
        case node@TreeNode(_, nodeVal, _) if nodeVal == recValToAdd => node
        case node@TreeNode(None, nodeVal, None) =>
          if (nodeVal <= recValToAdd) node.copy(right = Option(TreeNode(None, recValToAdd, None)))
          else node.copy(left = Option(TreeNode(None, recValToAdd, None)))
        case node@TreeNode(Some(ln), nodeVal, None) =>
          if (nodeVal <= recValToAdd) node.copy(right = Option(addRec(recValToAdd, ln)))
          else node.copy(left = Option(TreeNode(None, recValToAdd, None)))
        case node@TreeNode(None, nodeVal, Some(rn)) =>
          if (nodeVal <= recValToAdd) node.copy(right = Option(addRec(recValToAdd, rn)))
          else node.copy(left = Option(TreeNode(None, valToAdd, None)))
        case node@TreeNode(Some(ln), nodeVal, Some(rn)) =>
          if (nodeVal <= recValToAdd) node.copy(right = Option(addRec(recValToAdd, rn)))
          else node.copy(left = Option(addRec(recValToAdd, ln)))
      }
    }

    val updatedTreeNodes = addRec(valToAdd, rootNode)
    Tree(updatedTreeNodes)
  }

  def search(wantedVal: Int): Option[Int] = {
    @tailrec
    def recSearch(recWantedVal: Int, recNode: TreeNode): Option[Int] = {
      recNode match {
        case TreeNode(_, n, _) if n == recWantedVal => Option(recWantedVal)
        case TreeNode(None, _, None) => None
        case TreeNode(Some(ln), nodeVal, None) =>
          if (nodeVal <= recWantedVal) None
          else recSearch(recWantedVal, ln)
        case TreeNode(None, nodeVal, Some(rn)) =>
          if (nodeVal <= recWantedVal) recSearch(recWantedVal, rn)
          else None
        case TreeNode(Some(ln), nodeVal, Some(rn)) =>
          if (nodeVal <= recWantedVal) recSearch(recWantedVal, rn)
          else recSearch(recWantedVal, ln)
      }
    }

    recSearch(wantedVal, rootNode)
  }
}

object Tree {
  def empty = Tree(TreeNode.empty)
}