How to parse a table into a binary tree in Kotlin

1 Answer

0 votes
// ================================================================
// 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

*/

 



answered Sep 5 by avibootz
...