// ================================================================
// Parse a table of (id, name, parentId) into a binary tree using
// the Left‑Child / Right‑Sibling representation.
// ================================================================
data class Node(
val id: Int,
val name: String,
var left: Node? = null, // first child
var right: Node? = null // next sibling
)
data class Row(val id: Int, val name: String, val parentId: Int)
// ================================================================
// Print the tree with indentation and explicit ROOT markers
// ================================================================
fun printTree(node: Node?, depth: Int = 0) {
if (node == null) return
if (depth == 0) println("ROOT")
val indent = " ".repeat(depth + 1)
println("$indent${"%02d".format(node.id)} - ${node.name}")
printTree(node.left, depth + 1)
if (depth == 0)
printTree(node.right, 0)
else
printTree(node.right, depth)
}
// ================================================================
// Build the tree using Left‑Child / Right‑Sibling representation
// ================================================================
fun buildTree(table: List<Row>): Node? {
val nodes: Map<Int, Node> = table.associate { it.id to Node(it.id, it.name) }
var root: Node? = null
for (row in table) {
val current: Node = nodes[row.id]!!
if (row.parentId == 0) {
// top-level node → sibling chain under root
if (root == null) {
root = current
} else {
var p: Node = root // FIXED: removed unnecessary !!
while (p.right != null) p = p.right!!
p.right = current
}
} else {
val parent: Node = nodes[row.parentId]!!
if (parent.left == null) {
parent.left = current
} else {
var p: Node = parent.left!!
while (p.right != null) p = p.right!!
p.right = current
}
}
}
return root
}
// ================================================================
// Main Program
// ================================================================
fun main() {
// Id Name ParentId
val table = listOf(
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
*/