Pseudo-code for the design of our NestedSet Tree representation.

Tree.scala

case class Node(name:String, left:Int, children:Seq[Node] = Nil) {
  def right = 1 + left + children.lastOption.fold(0)(_.right)
}

var root = Node("root", 1) // (name, initial-left-value)

assert(root.left, 1)
assert(root.right, 2)

root = root ++ Seq(Node("A", 0), Node("B", 4), Node("C", 27))

assert(root.children.length, 3)

assert(root.left, 1)
assert(root.right, 8)

// Scala-ish pseudo-code, but there you go.
// The Left value of a doesn't matter when building a tree
//   (aside from the initial sorting of children) 
// as the children are deep-copied on assignment and their
// left is recalculated against a reduce operation:

children = children.foldLeft((Seq[Node](), left)) { (acc, left, child) =>
  val newLeft = left + 1
  (acc ++ child.copy(left = newLeft), newLeft)
}._1

// (That would be the body of a ++ method on Node.)

// The right value is always calculated:
right = 1 + this.left + children.last.right

// I'm not sure how I'd make this a "sparse" tree then.
// I'm sure it's possible, it's just non-obvious right now.