Question

How to parse a table into a binary tree in Scala

Answer 1

// ================================================================
// Parse a table of (id, name, parentId) into a binary tree using
// the Left‑Child / Right‑Sibling representation.
//
// Why this representation?
// - The table describes a general tree (each node can have many children).
// - A binary tree requires each node to have at most two pointers.
// - left  -> first child
// - right -> next sibling
//
// This preserves the full structure while staying inside a binary tree model.
// ================================================================

case class Node(
  id: Int,
  name: String,
  var left: Option[Node] = None,   // first child
  var right: Option[Node] = None   // next sibling
)

case class Row(id: Int, name: String, parentId: Int)

// ================================================================
// Print the tree with indentation and explicit ROOT markers
// ================================================================

def printTree(node: Option[Node], depth: Int = 0): Unit = {
  node match {
    case None => ()
    case Some(n) =>
      // Print ROOT on its own line
      if (depth == 0) println("ROOT")

      // Indent the node itself
      val indent = "  " * (depth + 1)

      // Print ID with leading zero if needed
      println(f"$indent${n.id}%02d - ${n.name}")

      // First child
      printTree(n.left, depth + 1)

      // Next sibling (another top-level node)
      if (depth == 0)
        printTree(n.right, 0) // restart ROOT
      else
        printTree(n.right, depth)
  }
}

// ================================================================
// Build the tree using Left‑Child / Right‑Sibling representation
// ================================================================

def buildTree(table: List[Row]): Option[Node] = {
  // Create nodes
  val nodes = table.map(r => r.id -> Node(r.id, r.name)).toMap

  var root: Option[Node] = None

  // Attach children and siblings
  table.foreach { row =>
    val current = nodes(row.id)

    if (row.parentId == 0) {
      // top-level node → sibling chain under root
      root match {
        case None =>
          root = Some(current)
        case Some(r) =>
          var p = r
          while (p.right.isDefined) p = p.right.get
          p.right = Some(current)
      }
    } else {
      val parent = nodes(row.parentId)

      // attach as first child or next sibling
      parent.left match {
        case None =>
          parent.left = Some(current)
        case Some(firstChild) =>
          var p = firstChild
          while (p.right.isDefined) p = p.right.get
          p.right = Some(current)
      }
    }
  }

  root
}

// ================================================================
// Main Program
// ================================================================

object Main {
  def main(args: Array[String]): Unit = {
    //    Id   Name            ParentId 
    val table = List(
      Row(1,  "Node 1",        0),
      Row(2,  "Node 1.1",      1),
      Row(3,  "Node 2",        0),
      Row(4,  "Node 1.1.1",    2),
      Row(5,  "Node 2.1",      3),
      Row(6,  "Node 2.3.1",    3),
      Row(7,  "Node 1.2",      1),
      Row(8,  "Node 1.3",      1),
      Row(9,  "Node 1.3.1",    8),
      Row(10, "Node 2.4",      3),
      Row(11, "Node 2.1.1",    5),
      Row(12, "Node 2.1.1.6",  11)
    )

    val root = buildTree(table)
    printTree(root)
  }
}


/*
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4

*/

 

70+ SQL courses for beginners and professionals