0
# Utility Functions
1

2
Helper functions for common tree operations including finding common ancestors, accessing sibling nodes, and performance-optimized cached search operations. These utilities provide convenient shortcuts for frequent tree manipulation tasks.
3

4
## Capabilities
5

6
### Ancestor and Relationship Utilities
7

8
#### commonancestors - Find Common Ancestors
9

10
Determine common ancestors of multiple nodes, useful for finding shared parent nodes and calculating relationships between tree branches.
11

12
```python { .api }
13
def commonancestors(*nodes):
14
    """
15
    Determine common ancestors of nodes.
16
    
17
    Args:
18
        *nodes: Variable number of nodes to find common ancestors for
19
        
20
    Returns:
21
        Tuple of common ancestor nodes from closest to root
22
    """
23
```
24

25
**Usage Example:**
26

27
```python
28
from anytree import Node, util
29

30
# Create tree structure
31
root = Node("Company")
32
engineering = Node("Engineering", parent=root)
33
marketing = Node("Marketing", parent=root)
34
backend = Node("Backend", parent=engineering)
35
frontend = Node("Frontend", parent=engineering)
36
content = Node("Content", parent=marketing)
37
social = Node("Social", parent=marketing)
38

39
# Find common ancestors of nodes in same subtree
40
backend_frontend_ancestors = util.commonancestors(backend, frontend)
41
print(f"Backend & Frontend ancestors: {[n.name for n in backend_frontend_ancestors]}")
42
# Output: ['Company', 'Engineering']
43

44
# Find common ancestors of nodes in different subtrees
45
backend_content_ancestors = util.commonancestors(backend, content)
46
print(f"Backend & Content ancestors: {[n.name for n in backend_content_ancestors]}")
47
# Output: ['Company']
48

49
# Common ancestors of multiple nodes
50
all_teams_ancestors = util.commonancestors(backend, frontend, content, social)
51
print(f"All teams ancestors: {[n.name for n in all_teams_ancestors]}")
52
# Output: ['Company']
53

54
# Single node (returns all ancestors)
55
single_ancestors = util.commonancestors(backend)
56
print(f"Backend ancestors: {[n.name for n in single_ancestors]}")
57
# Output: ['Company', 'Engineering']
58

59
# No nodes
60
no_ancestors = util.commonancestors()
61
print(f"No nodes ancestors: {no_ancestors}")
62
# Output: ()
63
```
64

65
### Sibling Navigation
66

67
#### leftsibling - Get Left Sibling
68

69
Return the left (previous) sibling of a node, useful for navigation and ordering operations.
70

71
```python { .api }
72
def leftsibling(node):
73
    """
74
    Return Left Sibling of node.
75
    
76
    Args:
77
        node: Node to find left sibling for
78
        
79
    Returns:
80
        Left sibling node or None if node is first child or root
81
    """
82
```
83

84
**Usage Example:**
85

86
```python
87
from anytree import Node, util
88

89
# Create ordered children
90
parent = Node("Parent")
91
first = Node("First", parent=parent)
92
second = Node("Second", parent=parent)
93
third = Node("Third", parent=parent)
94
fourth = Node("Fourth", parent=parent)
95

96
# Get left siblings
97
print(f"First left sibling: {util.leftsibling(first)}")    # None
98
print(f"Second left sibling: {util.leftsibling(second)}")  # Node('/Parent/First')
99
print(f"Third left sibling: {util.leftsibling(third)}")   # Node('/Parent/Second')
100
print(f"Fourth left sibling: {util.leftsibling(fourth)}") # Node('/Parent/Third')
101

102
# Root node has no sibling
103
print(f"Root left sibling: {util.leftsibling(parent)}")   # None
104
```
105

106
#### rightsibling - Get Right Sibling
107

108
Return the right (next) sibling of a node, useful for navigation and ordering operations.
109

110
```python { .api }
111
def rightsibling(node):
112
    """
113
    Return Right Sibling of node.
114
    
115
    Args:
116
        node: Node to find right sibling for
117
        
118
    Returns:
119
        Right sibling node or None if node is last child or root
120
    """
121
```
122

123
**Usage Example:**
124

125
```python
126
from anytree import Node, util
127

128
# Create ordered children
129
parent = Node("Parent")
130
first = Node("First", parent=parent)  
131
second = Node("Second", parent=parent)
132
third = Node("Third", parent=parent)
133
fourth = Node("Fourth", parent=parent)
134

135
# Get right siblings
136
print(f"First right sibling: {util.rightsibling(first)}")   # Node('/Parent/Second')
137
print(f"Second right sibling: {util.rightsibling(second)}") # Node('/Parent/Third')
138
print(f"Third right sibling: {util.rightsibling(third)}")  # Node('/Parent/Fourth')
139
print(f"Fourth right sibling: {util.rightsibling(fourth)}") # None
140

141
# Root node has no sibling
142
print(f"Root right sibling: {util.rightsibling(parent)}")  # None
143
```
144

145
## Cached Search Module
146

147
High-performance cached versions of search functions for repeated queries on the same tree structure. These functions provide significant performance improvements when performing multiple searches on static or slowly-changing trees.
148

149
### Performance-Optimized Search
150

151
```python { .api }
152
# Import cached search functions
153
from anytree import cachedsearch
154

155
# Cached versions of search functions with same signatures
156
def cachedsearch.find(node, filter_=None, stop=None, maxlevel=None): ...
157
def cachedsearch.find_by_attr(node, value, name="name", maxlevel=None): ...
158
def cachedsearch.findall(node, filter_=None, stop=None, maxlevel=None, mincount=None, maxcount=None): ...
159
def cachedsearch.findall_by_attr(node, value, name="name", maxlevel=None, mincount=None, maxcount=None): ...
160
```
161

162
**Usage Example:**
163

164
```python
165
from anytree import Node, cachedsearch
166
import time
167

168
# Create large tree for performance testing
169
def create_large_tree(depth=5, breadth=10):
170
    root = Node("root")
171
    
172
    def add_children(parent, current_depth):
173
        if current_depth >= depth:
174
            return
175
        
176
        for i in range(breadth):
177
            child = Node(f"{parent.name}_child_{i}", 
178
                        parent=parent,
179
                        level=current_depth,
180
                        category=f"cat_{i % 3}")
181
            add_children(child, current_depth + 1)
182
    
183
    add_children(root, 0)
184
    return root
185

186
large_tree = create_large_tree(depth=4, breadth=8)
187
print(f"Created tree with {len(list(large_tree.descendants)) + 1} nodes")
188

189
# Compare performance: regular vs cached search
190
def time_search(search_func, *args, **kwargs):
191
    start = time.time()
192
    result = search_func(*args, **kwargs)
193
    end = time.time()
194
    return result, end - start
195

196
# Regular search
197
from anytree import findall_by_attr
198
regular_results, regular_time = time_search(
199
    findall_by_attr, large_tree, "cat_1", name="category"
200
)
201

202
# First cached search (builds cache)
203
cached_results1, cached_time1 = time_search(
204
    cachedsearch.findall_by_attr, large_tree, "cat_1", name="category"
205
)
206

207
# Second cached search (uses cache)
208
cached_results2, cached_time2 = time_search(
209
    cachedsearch.findall_by_attr, large_tree, "cat_1", name="category"
210
)
211

212
print(f"Regular search: {regular_time:.4f}s")
213
print(f"First cached search: {cached_time1:.4f}s") 
214
print(f"Second cached search: {cached_time2:.4f}s")
215
print(f"Cache speedup: {regular_time/cached_time2:.1f}x")
216
print(f"Results identical: {len(regular_results) == len(cached_results2)}")
217
```
218

219
## Common Utility Patterns
220

221
### Tree Navigation Helpers
222

223
Build navigation utilities using sibling functions:
224

225
```python
226
from anytree import Node, util
227

228
class TreeNavigator:
229
    @staticmethod
230
    def get_siblings(node):
231
        """Get all siblings of a node (excluding the node itself)"""
232
        if not node.parent:
233
            return ()
234
        return tuple(child for child in node.parent.children if child != node)
235
    
236
    @staticmethod
237
    def get_sibling_by_offset(node, offset):
238
        """Get sibling at specified offset (negative for left, positive for right)"""
239
        if not node.parent:
240
            return None
241
            
242
        siblings = node.parent.children
243
        current_index = siblings.index(node)
244
        target_index = current_index + offset
245
        
246
        if 0 <= target_index < len(siblings):
247
            return siblings[target_index]
248
        return None
249
    
250
    @staticmethod
251
    def move_node(node, direction):
252
        """Move node left or right among siblings"""
253
        if direction == "left":
254
            left = util.leftsibling(node)
255
            if left:
256
                # Swap positions by manipulating parent's children
257
                parent = node.parent
258
                children = list(parent.children)
259
                node_idx = children.index(node)
260
                left_idx = children.index(left)
261
                children[node_idx], children[left_idx] = children[left_idx], children[node_idx]
262
                parent.children = children
263
                return True
264
        elif direction == "right":
265
            right = util.rightsibling(node)
266
            if right:
267
                # Similar swap logic
268
                parent = node.parent
269
                children = list(parent.children)
270
                node_idx = children.index(node)
271
                right_idx = children.index(right)
272
                children[node_idx], children[right_idx] = children[right_idx], children[node_idx]
273
                parent.children = children
274
                return True
275
        return False
276

277
# Example usage
278
parent = Node("Tasks")
279
task1 = Node("Task 1", parent=parent, priority=1)
280
task2 = Node("Task 2", parent=parent, priority=2)
281
task3 = Node("Task 3", parent=parent, priority=3)
282

283
navigator = TreeNavigator()
284

285
# Get all siblings of task2
286
siblings = navigator.get_siblings(task2)
287
print(f"Task 2 siblings: {[s.name for s in siblings]}")  # ['Task 1', 'Task 3']
288

289
# Get sibling by offset
290
prev_task = navigator.get_sibling_by_offset(task2, -1)  # Task 1
291
next_task = navigator.get_sibling_by_offset(task2, 1)   # Task 3
292
print(f"Previous: {prev_task.name}, Next: {next_task.name}")
293
```
294

295
### Common Ancestor Analysis
296

297
Use common ancestors for tree analysis and relationship detection:
298

299
```python
300
from anytree import Node, util
301

302
def analyze_relationships(nodes):
303
    """Analyze relationships between multiple nodes"""
304
    if len(nodes) < 2:
305
        return "Insufficient nodes for analysis"
306
    
307
    # Find common ancestors
308
    ancestors = util.commonancestors(*nodes)
309
    
310
    if not ancestors:
311
        return "Nodes are in separate trees"
312
    
313
    closest_ancestor = ancestors[-1]  # Last in tuple is closest to nodes
314
    
315
    # Calculate relationship metrics
316
    depths_from_ancestor = []
317
    for node in nodes:
318
        depth = 0
319
        current = node
320
        while current != closest_ancestor:
321
            current = current.parent
322
            depth += 1
323
        depths_from_ancestor.append(depth)
324
    
325
    analysis = {
326
        "common_ancestors": [a.name for a in ancestors],
327
        "closest_common_ancestor": closest_ancestor.name,
328
        "relationship_distances": dict(zip([n.name for n in nodes], depths_from_ancestor)),
329
        "max_distance": max(depths_from_ancestor),
330
        "are_siblings": len(set(n.parent for n in nodes if n.parent)) == 1,
331
        "are_cousins": len(ancestors) > 1 and all(d == 2 for d in depths_from_ancestor)
332
    }
333
    
334
    return analysis
335

336
# Example usage
337
company = Node("Company")
338
eng = Node("Engineering", parent=company)
339
mkt = Node("Marketing", parent=company)
340
backend = Node("Backend", parent=eng)
341
frontend = Node("Frontend", parent=eng)
342
content = Node("Content", parent=mkt)
343

344
# Analyze siblings
345
sibling_analysis = analyze_relationships([backend, frontend])
346
print("Sibling analysis:", sibling_analysis)
347

348
# Analyze cousins
349
cousin_analysis = analyze_relationships([backend, content])
350
print("Cousin analysis:", cousin_analysis)
351
```
352

353
### Tree Manipulation Utilities
354

355
Combine utilities for advanced tree manipulation:
356

357
```python
358
from anytree import Node, util
359

360
class TreeManipulator:
361
    @staticmethod
362
    def swap_siblings(node1, node2):
363
        """Swap two sibling nodes"""
364
        if node1.parent != node2.parent:
365
            raise ValueError("Nodes must be siblings")
366
        
367
        parent = node1.parent
368
        children = list(parent.children)
369
        idx1 = children.index(node1)
370
        idx2 = children.index(node2)
371
        children[idx1], children[idx2] = children[idx2], children[idx1]
372
        parent.children = children
373
    
374
    @staticmethod
375
    def sort_children(parent, key_func=None, reverse=False):
376
        """Sort children of a node"""
377
        if key_func is None:
378
            key_func = lambda n: n.name
379
        
380
        sorted_children = sorted(parent.children, key=key_func, reverse=reverse)
381
        parent.children = sorted_children
382
    
383
    @staticmethod
384
    def insert_between_siblings(new_node, left_sibling, right_sibling):
385
        """Insert new node between two siblings"""
386
        if left_sibling.parent != right_sibling.parent:
387
            raise ValueError("Siblings must have same parent")
388
        
389
        if util.rightsibling(left_sibling) != right_sibling:
390
            raise ValueError("Nodes must be adjacent siblings")
391
        
392
        parent = left_sibling.parent
393
        children = list(parent.children)
394
        right_idx = children.index(right_sibling)
395
        
396
        # Set parent and insert at correct position
397
        new_node.parent = parent
398
        children.insert(right_idx, new_node)
399
        parent.children = children
400

401
# Example usage
402
project = Node("Project")
403
phase1 = Node("Phase 1", parent=project)
404
phase3 = Node("Phase 3", parent=project)
405

406
manipulator = TreeManipulator()
407

408
# Insert phase 2 between phase 1 and 3
409
phase2 = Node("Phase 2")
410
manipulator.insert_between_siblings(phase2, phase1, phase3)
411

412
print(f"Project phases: {[child.name for child in project.children]}")
413
# Output: ['Phase 1', 'Phase 2', 'Phase 3']
414

415
# Sort children alphabetically
416
team = Node("Team")
417
Node("Charlie", parent=team, role="developer")
418
Node("Alice", parent=team, role="manager")
419
Node("Bob", parent=team, role="designer")
420

421
print(f"Before sort: {[child.name for child in team.children]}")
422
manipulator.sort_children(team)
423
print(f"After sort: {[child.name for child in team.children]}")
424
# Output: ['Alice', 'Bob', 'Charlie']
425
```
426

427
### Performance Optimization Helpers
428

429
Use cached search efficiently in applications:
430

431
```python
432
from anytree import Node, cachedsearch
433
from functools import lru_cache
434

435
class OptimizedTreeService:
436
    def __init__(self, root):
437
        self.root = root
438
        self._cache_warmed = False
439
    
440
    def warm_cache(self):
441
        """Pre-warm search cache with common queries"""
442
        if self._cache_warmed:
443
            return
444
        
445
        # Common searches to pre-cache
446
        cachedsearch.findall(self.root, filter_=lambda n: True)  # Cache all nodes
447
        
448
        # Cache searches by common attributes
449
        for attr_name in ['name', 'type', 'category', 'status']:
450
            try:
451
                cachedsearch.findall_by_attr(self.root, "", name=attr_name)
452
            except:
453
                pass  # Attribute might not exist
454
        
455
        self._cache_warmed = True
456
    
457
    @lru_cache(maxsize=128)
458
    def find_by_path(self, path_parts):
459
        """Cached path-based node finding"""
460
        current = self.root
461
        for part in path_parts:
462
            found = cachedsearch.find_by_attr(current, part, name="name")
463
            if not found:
464
                return None
465
            current = found
466
        return current
467
    
468
    def bulk_find(self, search_criteria):
469
        """Efficiently perform multiple searches"""
470
        self.warm_cache()
471
        
472
        results = {}
473
        for criterion_name, (filter_func, max_results) in search_criteria.items():
474
            matches = cachedsearch.findall(
475
                self.root, 
476
                filter_=filter_func,
477
                maxcount=max_results
478
            )
479
            results[criterion_name] = matches
480
        
481
        return results
482

483
# Example usage
484
# Create service tree
485
service_root = Node("Services")
486
web_service = Node("WebService", parent=service_root, type="web", status="active")
487
db_service = Node("DatabaseService", parent=service_root, type="database", status="active")
488
cache_service = Node("CacheService", parent=service_root, type="cache", status="inactive")
489

490
# Create optimized service
491
tree_service = OptimizedTreeService(service_root)
492

493
# Perform bulk searches
494
search_criteria = {
495
    "active_services": (lambda n: getattr(n, 'status', '') == 'active', 10),
496
    "web_services": (lambda n: getattr(n, 'type', '') == 'web', 5),
497
    "all_services": (lambda n: hasattr(n, 'type'), 100)
498
}
499

500
results = tree_service.bulk_find(search_criteria)
501
for category, nodes in results.items():
502
    print(f"{category}: {[n.name for n in nodes]}")
503
```
504

505
## Module Access Patterns
506

507
### Direct Utility Import
508

509
```python
510
# Import individual utility functions
511
from anytree.util import commonancestors, leftsibling, rightsibling
512

513
# Import utility module
514
from anytree import util
515

516
# Use utilities
517
ancestors = util.commonancestors(node1, node2)
518
left = util.leftsibling(node)
519
right = util.rightsibling(node)
520
```
521

522
### Cached Search Import
523

524
```python
525
# Import cached search module
526
from anytree import cachedsearch
527

528
# Use cached search functions
529
results = cachedsearch.findall_by_attr(root, "target", name="category")
530
node = cachedsearch.find(root, filter_=lambda n: n.value > 100)
531
```
532

533
## Best Practices
534

535
### When to Use Cached Search
536

537
- **Static or slowly-changing trees**: Maximum benefit from caching
538
- **Repeated similar queries**: Cache pays off with multiple searches
539
- **Large trees (1000+ nodes)**: Performance gains are significant
540
- **Interactive applications**: Better user experience with faster responses
541

542
### When to Use Regular Search
543

544
- **One-time queries**: Cache overhead not worth it
545
- **Frequently changing trees**: Cache invalidation overhead
546
- **Small trees (<100 nodes)**: Performance difference negligible
547
- **Memory-constrained environments**: Cache uses additional memory
548

549
### Utility Function Guidelines
550

551
- **Use `commonancestors`** for: relationship analysis, finding merge points, calculating distances
552
- **Use `leftsibling`/`rightsibling`** for: navigation UI, ordering operations, sequential processing
553
- **Combine utilities** for: complex tree manipulation, custom navigation logic, specialized algorithms