When I first started working with functional programming, I had a mental block regarding immutable data structures. I kept thinking: "If I have a Binary Search Tree with a million nodes and I want to add one single integer, I have to copy the entire million-node tree into a new memory location." It sounded absurdly inefficient. If that were true, we'd spend all our time triggering the garbage collector and copying bytes instead of actually running our business logic.

The "Deep Copy" Myth

The misconception is the belief that immutability requires a full deep copy of the structure for every mutation. To see why this is wrong, let's look at a conceptual example. Imagine a BST where the root is 50, the left child is 25, and the right child is 75. If you want to insert the value 80, you don't need to touch the node 25 or any of its descendants. They haven't changed. Why would you copy them?

In a mutable world, you'd just find the leaf and attach a new node. In an immutable world, you can't change the parent's reference, but you don't have to duplicate the parts of the tree that stay the same. This leads us to the actual mechanism we use in Scala.

Structural Sharing: The Secret Sauce

Instead of copying the whole tree, we use structural sharing. When we "update" an immutable tree, we only recreate the nodes along the path from the root to the point of change. Every other branch is shared between the old version of the tree and the new version.

Let's look at how we actually model this. I prefer using a sealed trait to define the tree, which forces us to handle both the empty and non-empty cases explicitly.

sealed trait BST {
  def insert(value: Int): BST
}

case object Empty extends BST {
  def insert(value: Int): BST = Node(value, Empty, Empty)
}

case class Node(value: Int, left: BST, right: BST) extends BST {
  def insert(newValue: Int): BST = {
    if (newValue < value) {
      // We create a new Node for the current level, 
      // but we REUSE the existing 'right' subtree.
      this.copy(left = left.insert(newValue))
    } else if (newValue > value) {
      // We REUSE the existing 'left' subtree.
      this.copy(right = right.insert(newValue))
    } else {
      // Value already exists; return this node as-is.
      this
    }
  }
}

Notice the this.copy(...) call. In the case where newValue < value, we are creating a new Node object. However, the right reference in that new node points to the exact same object in memory as the old node's right child. We've only allocated new memory for the nodes on the path down to the insertion point. In a balanced tree, that's only O(log n) nodes, not O(n).

Thinking Recursively About State

The trick to getting comfortable with this is to stop thinking about "changing" the tree and start thinking about "returning a new version" of the tree. When you call left.insert(newValue), you are asking the left subtree: "Give me a version of yourself that includes this value." Once the subtree provides that new version, you wrap it in a new parent node and pass it back up the call stack.

This pattern is incredibly powerful for concurrency. Because the old version of the tree is never modified, other threads can keep reading it without any locks or fear of data corruption while you are "creating" the new version. It's a trade-off: you use slightly more memory for the path nodes, but you gain total thread-safety and the ability to keep "snapshots" of your data structure over time.

📋 Practical Task

Implementing a BST Range-Search Filter

Now that you've mastered immutable insertions and structural sharing, let's implement a read-only operation. Your task is to add a method to the BST trait and its implementations called findRange(min: Int, max: Int): List[Int].

This method should return a list of all values in the tree that fall between min and max (inclusive), sorted in ascending order. To keep it efficient, you should not traverse branches that cannot possibly contain values within the range (for example, if the current node's value is already smaller than min, there is no need to search the left subtree).

Requirements:

• Update the BST trait to include the findRange signature.
• Implement findRange in Empty (should return an empty list).
• Implement findRange in Node using recursion.
• Ensure the resulting list is sorted (Hint: Think about the order of In-Order traversal).