| 11 | 11 | |
| 12 | 12 | |
| 13 | 13 | def BuildTree(records): |
| 14 | | root = None |
| 14 | if not records: |
| 15 | return None |
| 16 | |
| 17 | # Sort records by ID for validation |
| 15 | 18 | records.sort(key=lambda x: x.record_id) |
| 16 | | ordered_id = [i.record_id for i in records] |
| 17 | | if records: |
| 18 | | if ordered_id[-1] != len(ordered_id) - 1: |
| 19 | | raise ValueError('broken tree') |
| 20 | | if ordered_id[0] != 0: |
| 21 | | raise ValueError('invalid') |
| 22 | | trees = [] |
| 23 | | parent = {} |
| 24 | | for i in range(len(ordered_id)): |
| 25 | | for j in records: |
| 26 | | if ordered_id[i] == j.record_id: |
| 27 | | if j.record_id == 0: |
| 28 | | if j.parent_id != 0: |
| 29 | | raise ValueError('error!') |
| 30 | | if j.record_id < j.parent_id: |
| 31 | | raise ValueError('something went wrong!') |
| 32 | | if j.record_id == j.parent_id: |
| 33 | | if j.record_id != 0: |
| 34 | | raise ValueError('error!') |
| 35 | | trees.append(Node(ordered_id[i])) |
| 36 | | for i in range(len(ordered_id)): |
| 37 | | for j in trees: |
| 38 | | if i == j.node_id: |
| 39 | | parent = j |
| 40 | | for j in records: |
| 41 | | if j.parent_id == i: |
| 42 | | for k in trees: |
| 43 | | if k.node_id == 0: |
| 44 | | continue |
| 45 | | if j.record_id == k.node_id: |
| 46 | | child = k |
| 47 | | parent.children.append(child) |
| 48 | | if len(trees) > 0: |
| 49 | | root = trees[0] |
| 50 | | return root |
| 19 | |
| 20 | # Validate records |
| 21 | for i, record in enumerate(records): |
| 22 | if record.record_id != i: |
| 23 | raise ValueError("Record id is invalid or out of order.") |
| 24 | |
| 25 | # Validate parent-child relationships |
| 26 | for record in records: |
| 27 | if record.record_id == 0: |
| 28 | # Root node validation |
| 29 | if record.parent_id != 0: |
| 30 | raise ValueError("Node parent_id should be smaller than its record_id.") |
| 31 | else: |
| 32 | # Non-root node validation |
| 33 | if record.record_id == record.parent_id: |
| 34 | raise ValueError("Only root should have equal record and parent id.") |
| 35 | if record.record_id < record.parent_id: |
| 36 | raise ValueError("Node parent_id should be smaller than its record_id.") |
| 37 | |
| 38 | # Create nodes for all records |
| 39 | nodes = {} |
| 40 | for record in records: |
| 41 | nodes[record.record_id] = Node(record.record_id) |
| 42 | |
| 43 | # Build tree relationships - validate parent exists |
| 44 | for record in records: |
| 45 | if record.record_id != 0: # Skip root |
| 46 | if record.parent_id not in nodes: |
| 47 | raise KeyError(f"Parent node {record.parent_id} not found for record {record.record_id}") |
| 48 | parent_node = nodes[record.parent_id] |
| 49 | child_node = nodes[record.record_id] |
| 50 | parent_node.children.append(child_node) |
| 51 | |
| 52 | return nodes[0] if records else None |