How should I define the tree structure to make pattern matching easy?

When you're at a whiteboard, don't overcomplicate the data model. You want a structure that mirrors the recursive nature of the traversal itself. In Scala, the gold standard here is a sealed trait. By sealing the trait, you tell the compiler that all possible subtypes are defined in this file, which means the compiler can warn you if your match statement is missing a case.

sealed trait BinaryTree
case class Node(value: Int, left: BinaryTree, right: BinaryTree) extends BinaryTree
case object Empty extends BinaryTree

I prefer this over using null or optional types. With this setup, the "base case" of your recursion is simply the Empty object. It makes the code read almost like a mathematical definition, which is exactly what interviewers are looking for when they ask for a "functional" implementation.

What's the cleanest way to implement an in-order traversal?

In-order traversal (Left, Root, Right) is the classic example because if the tree is a Binary Search Tree, it returns the elements in sorted order. The trick is to avoid using a mutable ListBuffer. Instead, embrace the recursive nature of the tree. You want each call to return a list, and then you concatenate them.

def inOrder(tree: BinaryTree): List[Int] = tree match {
  case Empty => Nil
  case Node(v, left, right) => inOrder(left) ++ List(v) ++ inOrder(right)
}

Now, I'll be honest with you: the ++ operator creates a lot of intermediate lists. For a whiteboard interview, this is usually acceptable because it demonstrates you understand the algorithm. However, if the interviewer asks about performance, you'll need to talk about the accumulator pattern (which we'll touch on in a second).

How do I avoid the performance hit of list concatenation?

If you're dealing with a massive tree, ++ will kill your performance. To fix this, we use a helper function with an accumulator. Instead of returning a list and appending to it, we pass the "rest of the list" down into the recursive call. This allows us to use the :: (cons) operator, which is $O(1)$.

def inOrderEfficient(tree: BinaryTree): List[Int] = {
  def traverse(t: BinaryTree, acc: List[Int]): List[Int] = t match {
    case Empty => acc
    case Node(v, left, right) => 
      // We go right first, then root, then left, 
      // because we are building the list from the end backwards.
      traverse(left, v :: traverse(right, acc))
  }
  traverse(tree, Nil)
}

This pattern is a bit harder to wrap your head around at first. You're essentially saying: "Give me the traversal of the right subtree, stick the current value on the front of that, and then use that entire result as the starting point for the left subtree." It's a common functional idiom that saves you from $O(n^2)$ complexity in the worst case.

Wait, isn't this still going to blow the stack on a deep tree?

Yes, it is. In the examples above, the recursive calls aren't in the "tail position," meaning the program has to remember where it was to come back and finish the concatenation. In a production Scala environment, if you expect a tree to be 10,000 nodes deep, you'd either need to use scala.collection.immutable.Stack to simulate the recursion or use a Trampoline.

But here is a tip: on a whiteboard, don't start with the complex stack-safe version. Start with the simple recursive version I showed first. Once it's working, mention the stack overflow risk. It shows you're thinking about edge cases and production stability without making your initial code unreadable.

📋 Practical Task

Exercise: Implement a Post-Order Traversal

Using the BinaryTree sealed trait and case classes defined in the lesson, implement a function called postOrder. Unlike the in-order traversal, a post-order traversal must visit the nodes in this specific sequence: Left Subtree, Right Subtree, and finally the Root Node.

Your function should take a BinaryTree and return a List[Int]. Test your implementation with a tree that has at least three levels of depth to ensure your recursive calls are hitting the leaf nodes before returning the root values.