import Foundation
// ================================================================
// 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.
// ================================================================
final class Node {
let id: Int
let name: String
var left: Node? // first child
var right: Node? // next sibling
init(id: Int, name: String) {
self.id = id
self.name = name
self.left = nil
self.right = nil
}
}
struct Row {
let id: Int
let name: String
let parentId: Int
}
// ================================================================
// Print the tree with indentation and explicit ROOT markers
// ================================================================
func printTree(_ node: Node?, depth: Int = 0) {
guard let node = node else { return }
// Print ROOT on its own line
if depth == 0 {
print("ROOT")
}
// Indent the node itself
let indent = String(repeating: " ", count: depth + 1)
// Print ID with leading zero if needed
print("\(indent)\(String(format: "%02d", node.id)) - \(node.name)")
// First child
printTree(node.left, depth: depth + 1)
// Next sibling (another top-level node)
if depth == 0 {
printTree(node.right, depth: 0) // restart ROOT
} else {
printTree(node.right, depth: depth)
}
}
// ================================================================
// Build the tree using Left‑Child / Right‑Sibling representation
// ================================================================
func buildTree(_ table: [Row]) -> Node? {
// Create nodes
var nodes: [Int: Node] = [:]
for row in table {
nodes[row.id] = Node(id: row.id, name: row.name)
}
var root: Node? = nil
// Attach children and siblings
for row in table {
guard let current = nodes[row.id] else { continue }
if row.parentId == 0 {
// top-level node → sibling chain under root
if root == nil {
root = current
} else {
var p = root!
while let next = p.right {
p = next
}
p.right = current
}
} else {
guard let parent = nodes[row.parentId] else { continue }
// attach as first child or next sibling
if parent.left == nil {
parent.left = current
} else {
var p = parent.left!
while let next = p.right {
p = next
}
p.right = current
}
}
}
return root
}
// ================================================================
// Main Program
// ================================================================
let table: [Row] = [
Row(id: 1, name: "Node 1", parentId: 0),
Row(id: 2, name: "Node 1.1", parentId: 1),
Row(id: 3, name: "Node 2", parentId: 0),
Row(id: 4, name: "Node 1.1.1", parentId: 2),
Row(id: 5, name: "Node 2.1", parentId: 3),
Row(id: 6, name: "Node 2.3.1", parentId: 3),
Row(id: 7, name: "Node 1.2", parentId: 1),
Row(id: 8, name: "Node 1.3", parentId: 1),
Row(id: 9, name: "Node 1.3.1", parentId: 8),
Row(id: 10, name: "Node 2.4", parentId: 3),
Row(id: 11, name: "Node 2.1.1", parentId: 5),
Row(id: 12, name: "Node 2.1.1.6", parentId: 11)
]
let 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
*/
