"""
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.
"""
# -------------------- Node --------------------
class Node:
def __init__(self, id, name):
self.id = id
self.name = name
self.left = None # first child
self.right = None # next sibling
# -------------------- Print Tree --------------------
def print_tree(root, depth=0):
if root is None:
return
# Print ROOT on its own line
if depth == 0:
print("ROOT")
# Indent the node itself
print(" " * (depth + 1), end="")
# print ID with leading zero if needed
print(f"{root.id:02d} - {root.name}")
# first child
print_tree(root.left, depth + 1)
# next sibling (another top-level node)
if depth == 0 and root.right is not None:
print_tree(root.right, 0) # restart ROOT
else:
print_tree(root.right, depth)
# -------------------- Build Tree --------------------
def build_tree(table):
"""
table: list of dicts with keys: id, name, parentId
"""
# Create nodes
nodes = {row["id"]: Node(row["id"], row["name"]) for row in table}
root = None
# Attach children and siblings
for row in table:
id = row["id"]
parent_id = row["parentId"]
current = nodes[id]
if parent_id == 0:
# top-level node → sibling chain under root
if root is None:
root = current
else:
p = root
while p.right is not None:
p = p.right
p.right = current
else:
parent = nodes[parent_id]
# attach as first child or next sibling
if parent.left is None:
parent.left = current
else:
p = parent.left
while p.right is not None:
p = p.right
p.right = current
return root
# -------------------- Main --------------------
if __name__ == "__main__":
# Example table
table = [
{"id": 1, "name": "Node 1", "parentId": 0},
{"id": 2, "name": "Node 1.1", "parentId": 1},
{"id": 3, "name": "Node 2", "parentId": 0},
{"id": 4, "name": "Node 1.1.1", "parentId": 2},
{"id": 5, "name": "Node 2.1", "parentId": 3},
{"id": 6, "name": "Node 2.3.1", "parentId": 3},
{"id": 7, "name": "Node 1.2", "parentId": 1},
{"id": 8, "name": "Node 1.3", "parentId": 1},
{"id": 9, "name": "Node 1.3.1", "parentId": 8},
{"id": 10, "name": "Node 2.4", "parentId": 3},
{"id": 11, "name": "Node 2.1.1", "parentId": 5},
{"id": 12, "name": "Node 2.1.1.6", "parentId": 11},
]
# Build tree
root = build_tree(table)
# Print
print_tree(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
"""
