PYTHON
Represent Hierarchical Data with Dictionaries and Lists
Learn to effectively model and traverse tree-like hierarchical data structures, such as nested comments or categories, using Python's dictionaries and lists.
def build_tree(nodes, parent_id_key='parent_id', id_key='id', children_key='children'):
"""
Builds a tree structure from a flat list of nodes.
Each node in the list is expected to have an 'id' and a 'parent_id' (or similar).
"""
node_map = {node[id_key]: node for node in nodes}
tree = []
for node in nodes:
node.setdefault(children_key, []) # Ensure 'children' list exists
parent_id = node.get(parent_id_key)
if parent_id is None: # This is a root node
tree.append(node)
else:
parent = node_map.get(parent_id)
if parent:
parent.setdefault(children_key, []).append(node)
else:
# Handle orphaned nodes if parent_id exists but parent not found
# For this example, we'll treat them as roots
tree.append(node)
return tree
def print_tree(nodes, indent=0, children_key='children', label_key='name'):
"""Utility to print the tree structure."""
for node in nodes:
print(" " * indent + f"- {node.get(label_key, 'Node')}")
if node.get(children_key):
print_tree(node[children_key], indent + 1, children_key, label_key)
# Example usage: Web page comments
comments_flat = [
{'id': 1, 'parent_id': None, 'author': 'Alice', 'text': 'Great article!'},
{'id': 2, 'parent_id': 1, 'author': 'Bob', 'text': 'I agree, very insightful.'},
{'id': 3, 'parent_id': None, 'author': 'Charlie', 'text': 'Could you elaborate on point 3?'},
{'id': 4, 'parent_id': 2, 'author': 'David', 'text': 'Me too!'},
{'id': 5, 'parent_id': 3, 'author': 'Author', 'text': 'Sure, let me add an update.'},
{'id': 6, 'parent_id': None, 'author': 'Eve', 'text': 'Interesting perspective.'},
]
comment_tree = build_tree(comments_flat, id_key='id', parent_id_key='parent_id', children_key='replies')
print("
--- Comment Tree ---")
print_tree(comment_tree, label_key='text', children_key='replies')
# Example 2: Category hierarchy
categories_flat = [
{'name': 'Electronics', 'id': 'E', 'parent_id': None},
{'name': 'Computers', 'id': 'C', 'parent_id': 'E'},
{'name': 'Laptops', 'id': 'L', 'parent_id': 'C'},
{'name': 'Smartphones', 'id': 'S', 'parent_id': 'E'},
{'name': 'Accessories', 'id': 'A', 'parent_id': 'E'},
{'name': 'Keyboards', 'id': 'K', 'parent_id': 'A'},
]
category_tree = build_tree(categories_flat, id_key='id', parent_id_key='parent_id', children_key='subcategories')
print("
--- Category Tree ---")
print_tree(category_tree, label_key='name', children_key='subcategories')
How it works: Many web applications deal with hierarchical data, such as nested comments, file structures, or product categories. This snippet demonstrates how to transform a flat list of nodes (e.g., from a database query where each item has an `id` and a `parent_id`) into a nested tree structure using Python dictionaries and lists. It builds a `node_map` for efficient lookup of parent nodes and then iterates through the nodes to place children into their respective parent's `children` list, resulting in a flexible, deeply nested data structure suitable for rendering in UI or complex logic.