connect.scala

def connect(root: Node): Node = {
  def connectEdges(left: Node, right: Node): Unit = {
    if (left == null) return

    println(left.value)

    left.next = right
    connectEdges(left.right, right.left)
  }

  def visit(node: Node): Unit = {
    if (node == null || node.left == null) return

    println(node.value)

    node.left.next = node.right
    connectEdges(node.left.right, node.right.left)
    visit(node.left)
    visit(node.right)
  }

  visit(root)
  root
}