Idiomatic Scala Generics
When you feel yourself going to use a cast, especially when combined with an if on the save variable, then you most likely want to use a match.

def insert(node: Tree[Char], value: Char): Tree[Char] = {
  node match {
    case End =&gt; // hand end case here
    case n: Node[Char] =&gt; // handle the node case here
    case _ =&gt; // throw an exception, or do nothing if this case can't happen
  }
}


Now the node case is complicated enough that you might extract a method for it. Otherwise, it looked fine to me.