0
# Tree Traversal and Navigation
1
2
Comprehensive functionality for navigating and traversing tree structures using multiple algorithms including depth-first, breadth-first, and zigzag patterns. Provides efficient iteration, filtering, and path-finding capabilities.
3
4
## Capabilities
5
6
### Tree Traversal
7
8
Navigate trees using different traversal algorithms with customizable filtering and sorting.
9
10
```python { .api }
11
def expand_tree(nid=None, mode=DEPTH, filter=None, key=None, reverse=False, sorting=True) -> Iterator[str]:
12
"""
13
Traverse tree nodes in specified order yielding node identifiers.
14
15
Parameters:
16
- nid: str, starting node identifier (default: root)
17
- mode: int, traversal mode (DEPTH, WIDTH, ZIGZAG)
18
- filter: callable, function to filter nodes (node) -> bool
19
- key: callable, function for sorting nodes (node) -> comparable
20
- reverse: bool, reverse sort order
21
- sorting: bool, enable/disable sorting
22
23
Returns:
24
Iterator[str], node identifiers in traversal order
25
"""
26
27
def rsearch(nid, filter=None) -> Iterator[str]:
28
"""
29
Traverse from node to root (reverse search).
30
31
Parameters:
32
- nid: str, starting node identifier
33
- filter: callable, function to filter nodes (node) -> bool
34
35
Returns:
36
Iterator[str], node identifiers from node to root
37
"""
38
```
39
40
**Usage Examples:**
41
42
```python
43
# Depth-first traversal (default)
44
for node_id in tree.expand_tree():
45
print(f"Visiting: {tree[node_id].tag}")
46
47
# Breadth-first traversal
48
for node_id in tree.expand_tree(mode=Tree.WIDTH):
49
level = tree.level(node_id)
50
print(f"Level {level}: {tree[node_id].tag}")
51
52
# Zigzag traversal
53
for node_id in tree.expand_tree(mode=Tree.ZIGZAG):
54
print(f"Zigzag order: {tree[node_id].tag}")
55
56
# Start from specific node
57
for node_id in tree.expand_tree(nid="engineering"):
58
print(f"Subtree: {tree[node_id].tag}")
59
60
# With filtering and sorting
61
for node_id in tree.expand_tree(
62
filter=lambda node: node.is_leaf(tree.identifier),
63
key=lambda node: node.tag,
64
reverse=True
65
):
66
print(f"Leaf (sorted): {tree[node_id].tag}")
67
68
# Path from node to root
69
for ancestor_id in tree.rsearch("employee_1"):
70
print(f"Ancestor: {tree[ancestor_id].tag}")
71
```
72
73
### Structure Queries
74
75
Query tree structure and relationships between nodes.
76
77
```python { .api }
78
def children(nid) -> list[Node]:
79
"""
80
Get direct children of a node.
81
82
Parameters:
83
- nid: str, parent node identifier
84
85
Returns:
86
list[Node], list of child Node objects
87
"""
88
89
def is_branch(nid) -> list[str]:
90
"""
91
Get child node identifiers.
92
93
Parameters:
94
- nid: str, parent node identifier
95
96
Returns:
97
list[str], list of child node identifiers
98
"""
99
100
def parent(nid) -> Node | None:
101
"""
102
Get parent node object.
103
104
Parameters:
105
- nid: str, child node identifier
106
107
Returns:
108
Node object or None if root/not found
109
"""
110
111
def siblings(nid) -> list[Node]:
112
"""
113
Get sibling nodes (nodes with same parent).
114
115
Parameters:
116
- nid: str, node identifier
117
118
Returns:
119
list[Node], list of sibling Node objects
120
"""
121
122
def leaves(nid=None) -> list[Node]:
123
"""
124
Get all leaf nodes (nodes with no children).
125
126
Parameters:
127
- nid: str, subtree root (default: entire tree)
128
129
Returns:
130
list[Node], list of leaf Node objects
131
"""
132
```
133
134
**Usage Examples:**
135
136
```python
137
# Get children
138
engineering_team = tree.children("engineering")
139
for member in engineering_team:
140
print(f"Team member: {member.tag}")
141
142
# Get child identifiers
143
child_ids = tree.is_branch("engineering")
144
print(f"Child IDs: {child_ids}")
145
146
# Get parent
147
manager = tree.parent("alice")
148
if manager:
149
print(f"Alice's manager: {manager.tag}")
150
151
# Get siblings
152
coworkers = tree.siblings("alice")
153
for coworker in coworkers:
154
print(f"Coworker: {coworker.tag}")
155
156
# Get all leaf nodes
157
leaves = tree.leaves()
158
individual_contributors = [leaf.tag for leaf in leaves]
159
print(f"Individual contributors: {individual_contributors}")
160
161
# Get leaves in subtree
162
eng_leaves = tree.leaves("engineering")
163
```
164
165
### Tree Metrics and Analysis
166
167
Analyze tree structure and compute various metrics.
168
169
```python { .api }
170
def size(level=None) -> int:
171
"""
172
Get number of nodes in tree or at specific level.
173
174
Parameters:
175
- level: int, specific level to count (optional)
176
177
Returns:
178
int, number of nodes
179
"""
180
181
def depth(node=None) -> int:
182
"""
183
Get maximum depth of tree or depth of specific node.
184
185
Parameters:
186
- node: Node object or str, specific node (optional)
187
188
Returns:
189
int, depth value
190
"""
191
192
def level(nid, filter=None) -> int:
193
"""
194
Get level/depth of specific node.
195
196
Parameters:
197
- nid: str, node identifier
198
- filter: callable, filtering function (optional)
199
200
Returns:
201
int, level/depth of node (root is level 0)
202
"""
203
```
204
205
**Usage Examples:**
206
207
```python
208
# Total tree size
209
total_nodes = tree.size()
210
print(f"Total employees: {total_nodes}")
211
212
# Size at specific level
213
managers = tree.size(level=1)
214
print(f"Number of managers: {managers}")
215
216
# Tree depth
217
max_depth = tree.depth()
218
print(f"Organization depth: {max_depth}")
219
220
# Node level
221
alice_level = tree.level("alice")
222
print(f"Alice is at level: {alice_level}")
223
224
# Depth from specific node
225
subtree_depth = tree.depth(tree["engineering"])
226
print(f"Engineering dept depth: {subtree_depth}")
227
```
228
229
### Relationship Analysis
230
231
Analyze relationships and ancestry between nodes.
232
233
```python { .api }
234
def is_ancestor(ancestor, grandchild) -> bool:
235
"""
236
Check if one node is ancestor of another.
237
238
Parameters:
239
- ancestor: str, potential ancestor node identifier
240
- grandchild: str, potential descendant node identifier
241
242
Returns:
243
bool, True if ancestor relationship exists
244
"""
245
246
def ancestor(nid, level=None) -> str | None:
247
"""
248
Get ancestor at specific level or immediate ancestor.
249
250
Parameters:
251
- nid: str, node identifier
252
- level: int, ancestor level (optional)
253
254
Returns:
255
str, ancestor node identifier or None
256
"""
257
```
258
259
**Usage Examples:**
260
261
```python
262
# Check ancestry
263
if tree.is_ancestor("company", "alice"):
264
print("Alice works for the company")
265
266
# Get specific level ancestor
267
dept_manager = tree.ancestor("alice", level=1)
268
if dept_manager:
269
print(f"Alice's department: {tree[dept_manager].tag}")
270
271
# Get immediate parent (ancestor without level)
272
immediate_parent = tree.ancestor("alice")
273
```
274
275
### Path Operations
276
277
Find and analyze paths between nodes.
278
279
```python { .api }
280
def paths_to_leaves() -> list[list[str]]:
281
"""
282
Get all paths from root to leaf nodes.
283
284
Returns:
285
list[list[str]], list of paths (each path is list of node identifiers)
286
"""
287
```
288
289
**Usage Examples:**
290
291
```python
292
# Get all root-to-leaf paths
293
all_paths = tree.paths_to_leaves()
294
for path in all_paths:
295
path_names = [tree[nid].tag for nid in path]
296
print(f"Path: {' -> '.join(path_names)}")
297
298
# Find paths to specific conditions
299
leaf_paths = []
300
for path in tree.paths_to_leaves():
301
leaf_node = tree[path[-1]]
302
if leaf_node.data and leaf_node.data.get("role") == "engineer":
303
leaf_paths.append(path)
304
```
305
306
### Advanced Traversal Patterns
307
308
Complex traversal patterns and custom navigation logic.
309
310
**Usage Examples:**
311
312
```python
313
# Custom traversal with state tracking
314
visited = set()
315
for node_id in tree.expand_tree():
316
if node_id not in visited:
317
node = tree[node_id]
318
print(f"First visit: {node.tag}")
319
visited.add(node_id)
320
321
# Level-order processing
322
current_level = 0
323
for node_id in tree.expand_tree(mode=Tree.WIDTH):
324
node_level = tree.level(node_id)
325
if node_level != current_level:
326
print(f"\n--- Level {node_level} ---")
327
current_level = node_level
328
print(f" {tree[node_id].tag}")
329
330
# Conditional subtree traversal
331
def should_explore_subtree(node):
332
return node.data and node.data.get("active", True)
333
334
for node_id in tree.expand_tree(filter=lambda n: should_explore_subtree(n)):
335
print(f"Active branch: {tree[node_id].tag}")
336
337
# Reverse depth-first (post-order style)
338
nodes = list(tree.expand_tree())
339
for node_id in reversed(nodes):
340
print(f"Post-order: {tree[node_id].tag}")
341
```
342
343
## Traversal Constants
344
345
```python { .api }
346
ROOT = 0 # Tree traversal starting from root level
347
DEPTH = 1 # Depth-first traversal mode (pre-order)
348
WIDTH = 2 # Breadth-first traversal mode (level-order)
349
ZIGZAG = 3 # Zigzag traversal mode (alternating left-right)
350
```
351
352
## Performance Considerations
353
354
- **expand_tree()**: O(n) for full traversal, memory-efficient iterator
355
- **children()**: O(1) lookup, returns list copy
356
- **parent()**: O(1) lookup via internal node references
357
- **level()**: O(h) where h is tree height
358
- **is_ancestor()**: O(h) traversal up ancestry chain
359
- **paths_to_leaves()**: O(n*h) generates all paths
360
361
**Optimization Tips:**
362
363
```python
364
# Use iterators for large trees
365
for node_id in tree.expand_tree(): # Memory efficient
366
process_node(tree[node_id])
367
368
# Cache expensive operations
369
tree_depth = tree.depth() # Cache if used multiple times
370
leaf_nodes = tree.leaves() # Cache for repeated access
371
372
# Filter early for better performance
373
large_projects = tree.expand_tree(
374
filter=lambda n: n.data and n.data.get("size", 0) > 1000
375
)
376
```