0
# Tree Navigation
1

2
Methods for traversing tree structures, getting related nodes, and querying tree relationships. These navigation methods work consistently across all tree implementations and are optimized for each algorithm's strengths.
3

4
## Capabilities
5

6
### Parent and Root Access
7

8
Methods for accessing parent nodes and tree roots.
9

10
```python { .api }
11
def get_parent(self, update=False):
12
    """
13
    Get the parent node of this node.
14
    
15
    Parameters:
16
        update (bool): Whether to refresh from database
17
        
18
    Returns:
19
        Node or None: Parent node, or None if this is a root node
20
    """
21

22
def get_root(self):
23
    """
24
    Get the root node of this tree.
25
    
26
    Returns:
27
        Node: The root node of the tree containing this node
28
    """
29
```
30

31
Usage examples:
32
```python
33
# Get parent
34
parent = child_node.get_parent()
35
if parent:
36
    print(f"Parent: {parent.name}")
37
else:
38
    print("This is a root node")
39

40
# Get root of current tree
41
root = any_node.get_root()
42
print(f"Tree root: {root.name}")
43
```
44

45
### Children Access
46

47
Methods for accessing direct child nodes.
48

49
```python { .api }
50
def get_children(self):
51
    """
52
    Get queryset of direct child nodes.
53
    
54
    Returns:
55
        QuerySet: Direct children of this node, ordered appropriately
56
    """
57

58
def get_children_count(self):
59
    """
60
    Get count of direct child nodes.
61
    
62
    Returns:
63
        int: Number of direct children
64
    """
65

66
def get_first_child(self):
67
    """
68
    Get the first (leftmost) child node.
69
    
70
    Returns:
71
        Node or None: First child node, or None if no children
72
    """
73

74
def get_last_child(self):
75
    """
76
    Get the last (rightmost) child node.
77
    
78
    Returns:
79
        Node or None: Last child node, or None if no children
80
    """
81
```
82

83
Usage examples:
84
```python
85
# Get all children
86
children = parent.get_children()
87
for child in children:
88
    print(f"Child: {child.name}")
89

90
# Check if node has children
91
if parent.get_children_count() > 0:
92
    print("Node has children")
93

94
# Get specific child positions
95
first = parent.get_first_child()
96
last = parent.get_last_child()
97
```
98

99
### Sibling Access
100

101
Methods for accessing sibling nodes at the same tree level.
102

103
```python { .api }
104
def get_siblings(self):
105
    """
106
    Get queryset of all sibling nodes, including this node.
107
    
108
    Returns:
109
        QuerySet: All nodes at same level, including self
110
    """
111

112
def get_first_sibling(self):
113
    """
114
    Get the first (leftmost) sibling node.
115
    
116
    Returns:
117
        Node: First sibling (may be self if this is first)
118
    """
119

120
def get_last_sibling(self):
121
    """
122
    Get the last (rightmost) sibling node.
123
    
124
    Returns:
125
        Node: Last sibling (may be self if this is last)
126
    """
127

128
def get_prev_sibling(self):
129
    """
130
    Get the previous (left) sibling node.
131
    
132
    Returns:
133
        Node or None: Previous sibling, or None if this is first
134
    """
135

136
def get_next_sibling(self):
137
    """
138
    Get the next (right) sibling node.
139
    
140
    Returns:
141
        Node or None: Next sibling, or None if this is last
142
    """
143
```
144

145
Usage examples:
146
```python
147
# Get all siblings (including self)
148
siblings = node.get_siblings()
149
print(f"Total siblings: {siblings.count()}")
150

151
# Navigate between siblings
152
prev_node = node.get_prev_sibling()
153
next_node = node.get_next_sibling()
154

155
# Get sibling boundaries
156
first_sibling = node.get_first_sibling()
157
last_sibling = node.get_last_sibling()
158
```
159

160
### Ancestor Access
161

162
Methods for accessing ancestor nodes up the tree hierarchy.
163

164
```python { .api }
165
def get_ancestors(self):
166
    """
167
    Get queryset of all ancestor nodes.
168
    
169
    Returns nodes from root down to immediate parent.
170
    
171
    Returns:
172
        QuerySet: All ancestor nodes, ordered from root to parent
173
    """
174
```
175

176
Usage examples:
177
```python
178
# Get all ancestors
179
ancestors = node.get_ancestors()
180
for ancestor in ancestors:
181
    print(f"Ancestor: {ancestor.name}")
182

183
# Build breadcrumb navigation
184
breadcrumbs = []
185
for ancestor in node.get_ancestors():
186
    breadcrumbs.append(ancestor.name)
187
breadcrumbs.append(node.name)
188
print(" > ".join(breadcrumbs))
189

190
# Check if node has ancestors
191
if node.get_ancestors().exists():
192
    print("Node is not a root")
193
```
194

195
### Descendant Access
196

197
Methods for accessing descendant nodes down the tree hierarchy.
198

199
```python { .api }
200
def get_descendants(self):
201
    """
202
    Get queryset of all descendant nodes.
203
    
204
    Returns all nodes in the subtree rooted at this node,
205
    excluding this node itself.
206
    
207
    Returns:
208
        QuerySet: All descendant nodes in depth-first order
209
    """
210

211
def get_descendant_count(self):
212
    """
213
    Get count of all descendant nodes.
214
    
215
    Returns:
216
        int: Total number of descendants
217
    """
218
```
219

220
Usage examples:
221
```python
222
# Get all descendants
223
descendants = node.get_descendants()
224
print(f"Total descendants: {descendants.count()}")
225

226
# Process entire subtree
227
for descendant in descendants:
228
    print(f"Descendant: {descendant.name} (depth: {descendant.get_depth()})")
229

230
# Quick count check
231
if node.get_descendant_count() > 100:
232
    print("Large subtree - consider pagination")
233
```
234

235
### Depth and Level Information
236

237
Methods for determining node position in tree hierarchy.
238

239
```python { .api }
240
def get_depth(self):
241
    """
242
    Get the depth/level of this node in the tree.
243
    
244
    Root nodes have depth 0, their children have depth 1, etc.
245
    
246
    Returns:
247
        int: Depth level (0 for root nodes)
248
    """
249
```
250

251
Usage examples:
252
```python
253
# Get node depth
254
depth = node.get_depth()
255
print(f"Node depth: {depth}")
256

257
# Create indented display
258
indent = "  " * node.get_depth()
259
print(f"{indent}{node.name}")
260

261
# Filter by depth level
262
shallow_nodes = Category.objects.filter(depth__lte=2)
263
```
264

265
### Node Relationship Tests
266

267
Methods for testing relationships between nodes.
268

269
```python { .api }
270
def is_root(self):
271
    """
272
    Check if this node is a root node.
273
    
274
    Returns:
275
        bool: True if node has no parent
276
    """
277

278
def is_leaf(self):
279
    """
280
    Check if this node is a leaf node (has no children).
281
    
282
    Returns:
283
        bool: True if node has no children
284
    """
285

286
def is_sibling_of(self, node):
287
    """
288
    Check if this node is a sibling of another node.
289
    
290
    Parameters:
291
        node (Node): Node to test relationship with
292
        
293
    Returns:
294
        bool: True if nodes are siblings (same parent)
295
    """
296

297
def is_child_of(self, node):
298
    """
299
    Check if this node is a child of another node.
300
    
301
    Parameters:
302
        node (Node): Potential parent node
303
        
304
    Returns:
305
        bool: True if this node is direct child of given node
306
    """
307

308
def is_descendant_of(self, node):
309
    """
310
    Check if this node is a descendant of another node.
311
    
312
    Parameters:
313
        node (Node): Potential ancestor node
314
        
315
    Returns:
316
        bool: True if this node is descendant of given node
317
    """
318
```
319

320
Usage examples:
321
```python
322
# Test node types
323
if node.is_root():
324
    print("This is a root node")
325

326
if node.is_leaf():
327
    print("This is a leaf node")
328

329
# Test relationships
330
if child.is_child_of(parent):
331
    print("Direct parent-child relationship")
332

333
if grandchild.is_descendant_of(grandparent):
334
    print("Descendant relationship exists")
335

336
if node1.is_sibling_of(node2):
337
    print("Nodes are siblings")
338
```
339

340
## Advanced Navigation
341

342
### Tree Traversal Patterns
343

344
Get complete tree structures with annotation and formatting.
345

346
```python { .api }
347
@classmethod
348
def get_tree(cls, parent=None):
349
    """
350
    Get tree as depth-first ordered list of nodes.
351
    
352
    Parameters:
353
        parent (Node, optional): Root node to start from
354
        
355
    Returns:
356
        list: List of nodes in depth-first traversal order
357
    """
358

359
@classmethod
360
def get_annotated_list(cls, parent=None, max_depth=None):
361
    """
362
    Get annotated tree list with depth and formatting info.
363
    
364
    Parameters:
365
        parent (Node, optional): Root node to start from  
366
        max_depth (int, optional): Maximum depth to include
367
        
368
    Returns:
369
        list: List of dicts with node and annotation data
370
    """
371

372
@classmethod
373
def get_annotated_list_qs(cls, qs):
374
    """
375
    Get annotated list from existing queryset.
376
    
377
    Parameters:
378
        qs (QuerySet): Pre-filtered queryset of nodes
379
        
380
    Returns:
381
        list: Annotated list with depth and formatting info
382
    """
383
```
384

385
Usage examples:
386
```python
387
# Get complete tree structure
388
tree_nodes = Category.get_tree()
389
for node in tree_nodes:
390
    indent = "  " * node.get_depth()
391
    print(f"{indent}{node.name}")
392

393
# Get annotated tree with metadata
394
annotated = Category.get_annotated_list(max_depth=3)
395
for item in annotated:
396
    node = item['node']
397
    print(f"{'  ' * item['level']}{node.name} ({item['open']}/{item['close']})")
398

399
# Work with filtered queryset
400
active_categories = Category.objects.filter(active=True)
401
annotated_active = Category.get_annotated_list_qs(active_categories)
402
```
403

404
### Descendant Group Counting
405

406
Get sibling nodes with descendant count information.
407

408
```python { .api }
409
@classmethod  
410
def get_descendants_group_count(cls, parent=None):
411
    """
412
    Get siblings with descendant count information.
413
    
414
    Parameters:
415
        parent (Node, optional): Parent node (None for roots)
416
        
417
    Returns:
418
        QuerySet: Sibling nodes annotated with descendant counts
419
    """
420
```
421

422
Usage example:
423
```python
424
# Get root nodes with descendant counts
425
roots_with_counts = Category.get_descendants_group_count()
426
for root in roots_with_counts:
427
    print(f"{root.name}: {root.descendants_count} total items")
428

429
# Get children of specific node with counts
430
children_with_counts = Category.get_descendants_group_count(parent=electronics)
431
for child in children_with_counts:
432
    print(f"{child.name}: {child.descendants_count} subitems")
433
```
434

435
## Performance Considerations
436

437
### Implementation Differences
438

439
**AL_Node (Adjacency List)**:
440
- `get_ancestors()`: Requires recursive queries (O(depth))
441
- `get_descendants()`: Requires recursive queries (O(subtree_size))
442
- `get_children()`: Very efficient (O(1) query)
443
- `get_parent()`: Very efficient (cached or O(1))
444

445
**MP_Node (Materialized Path)**:
446
- `get_ancestors()`: Efficient path prefix query (O(1))
447
- `get_descendants()`: Efficient path prefix query (O(1))
448
- `get_children()`: Efficient path-based query (O(1))
449
- `get_parent()`: Efficient path manipulation (O(1))
450

451
**NS_Node (Nested Sets)**:
452
- `get_ancestors()`: Very efficient range query (O(1))
453
- `get_descendants()`: Very efficient range query (O(1))
454
- `get_children()`: Efficient with proper indexing (O(1))
455
- `get_parent()`: Efficient range query (O(1))
456

457
### Optimization Tips
458

459
```python
460
# Use select_related for parent access
461
nodes = Category.objects.select_related('parent')
462
for node in nodes:
463
    parent = node.get_parent()  # No additional query
464

465
# Use prefetch_related for children
466
parents = Category.objects.prefetch_related('children')
467
for parent in parents:
468
    children = parent.get_children()  # Uses prefetched data
469

470
# Cache depth calculations for display
471
nodes_with_depth = Category.objects.extra(select={'cached_depth': 'depth'})
472

473
# Limit descendant queries for large trees
474
shallow_descendants = node.get_descendants().filter(depth__lte=node.get_depth() + 2)
475
```
476

477
### Memory Usage
478

479
For large trees, consider pagination or limiting depth:
480

481
```python
482
# Paginate large descendant sets
483
from django.core.paginator import Paginator
484

485
descendants = node.get_descendants()
486
paginator = Paginator(descendants, 50)
487
page = paginator.get_page(1)
488

489
# Limit depth for navigation
490
max_nav_depth = 3
491
nav_nodes = Category.objects.filter(depth__lte=max_nav_depth)
492
```