0
# Tree Traversal and Iteration
1

2
Multiple iteration strategies for traversing tree structures. This module provides different traversal algorithms with filtering and depth control options for comprehensive tree navigation.
3

4
## Capabilities
5

6
### PreOrderIter - Pre-order Traversal
7

8
Iterates over tree using pre-order strategy: visits node first, then its children. This is depth-first traversal where parent nodes are processed before their children.
9

10
```python { .api }
11
class PreOrderIter(AbstractIter):
12
    """
13
    Pre-order tree iteration (node, then children).
14
    
15
    Args:
16
        node: Starting node for iteration
17
        filter_: Function called with every node as argument, node is returned if True
18
        stop: Stop iteration at node if stop function returns True for node  
19
        maxlevel: Maximum descending in the node hierarchy
20
    """
21
    def __init__(self, node, filter_=None, stop=None, maxlevel=None): ...
22
```
23

24
**Usage Example:**
25

26
```python
27
from anytree import Node, PreOrderIter
28

29
root = Node("root")
30
sub0 = Node("sub0", parent=root)
31
sub0sub0 = Node("sub0sub0", parent=sub0)
32
sub0sub1 = Node("sub0sub1", parent=sub0)
33
sub1 = Node("sub1", parent=root)
34

35
# Basic pre-order iteration
36
for node in PreOrderIter(root):
37
    print(node.name)
38
# Output: root, sub0, sub0sub0, sub0sub1, sub1
39

40
# With filter
41
for node in PreOrderIter(root, filter_=lambda n: "sub0" in n.name):
42
    print(node.name)
43
# Output: sub0, sub0sub0, sub0sub1
44

45
# With max level
46
for node in PreOrderIter(root, maxlevel=2):
47
    print(f"{'  ' * node.depth}{node.name}")
48
```
49

50
### PostOrderIter - Post-order Traversal
51

52
Iterates over tree using post-order strategy: visits children first, then the node. Useful for operations that need to process children before parents (like deletion, size calculation).
53

54
```python { .api }
55
class PostOrderIter(AbstractIter):
56
    """
57
    Post-order tree iteration (children, then node).
58
    
59
    Args:
60
        node: Starting node for iteration
61
        filter_: Function called with every node as argument, node is returned if True
62
        stop: Stop iteration at node if stop function returns True for node
63
        maxlevel: Maximum descending in the node hierarchy
64
    """
65
    def __init__(self, node, filter_=None, stop=None, maxlevel=None): ...
66
```
67

68
**Usage Example:**
69

70
```python
71
from anytree import Node, PostOrderIter
72

73
root = Node("root")
74
sub0 = Node("sub0", parent=root)  
75
sub0sub0 = Node("sub0sub0", parent=sub0)
76
sub0sub1 = Node("sub0sub1", parent=sub0)
77
sub1 = Node("sub1", parent=root)
78

79
# Post-order iteration - children before parents
80
for node in PostOrderIter(root):
81
    print(node.name)
82
# Output: sub0sub0, sub0sub1, sub0, sub1, root
83

84
# Calculate subtree sizes using post-order
85
def calculate_sizes(node):
86
    for n in PostOrderIter(node):
87
        n.size = 1 + sum(child.size for child in n.children)
88
    return node.size
89

90
size = calculate_sizes(root)
91
print(f"Total nodes: {size}")
92
```
93

94
### LevelOrderIter - Level-order Traversal
95

96
Iterates over tree using level-order (breadth-first) strategy: visits all nodes at depth N before visiting nodes at depth N+1.
97

98
```python { .api }
99
class LevelOrderIter(AbstractIter):
100
    """
101
    Level-order tree iteration (breadth-first).
102
    
103
    Args:
104
        node: Starting node for iteration
105
        filter_: Function called with every node as argument, node is returned if True
106
        stop: Stop iteration at node if stop function returns True for node
107
        maxlevel: Maximum descending in the node hierarchy
108
    """
109
    def __init__(self, node, filter_=None, stop=None, maxlevel=None): ...
110
```
111

112
**Usage Example:**
113

114
```python
115
from anytree import Node, LevelOrderIter
116

117
root = Node("root")
118
sub0 = Node("sub0", parent=root)
119
sub1 = Node("sub1", parent=root)
120
sub0sub0 = Node("sub0sub0", parent=sub0)
121
sub0sub1 = Node("sub0sub1", parent=sub0)
122
sub1sub0 = Node("sub1sub0", parent=sub1)
123

124
# Level-order iteration - breadth-first
125
for node in LevelOrderIter(root):
126
    print(f"Level {node.depth}: {node.name}")
127
# Output:
128
# Level 0: root
129
# Level 1: sub0
130
# Level 1: sub1  
131
# Level 2: sub0sub0
132
# Level 2: sub0sub1
133
# Level 2: sub1sub0
134
```
135

136
### LevelOrderGroupIter - Grouped Level-order
137

138
Iterates over tree using level-order strategy but returns groups of nodes for each level. Each iteration yields a tuple of all nodes at the current depth.
139

140
```python { .api }
141
class LevelOrderGroupIter(AbstractIter):
142
    """
143
    Level-order tree iteration returning groups for each level.
144
    
145
    Args:
146
        node: Starting node for iteration
147
        filter_: Function called with every node as argument, node is returned if True
148
        stop: Stop iteration at node if stop function returns True for node
149
        maxlevel: Maximum descending in the node hierarchy
150
    """
151
    def __init__(self, node, filter_=None, stop=None, maxlevel=None): ...
152
```
153

154
**Usage Example:**
155

156
```python
157
from anytree import Node, LevelOrderGroupIter
158

159
root = Node("root")
160
sub0 = Node("sub0", parent=root)
161
sub1 = Node("sub1", parent=root) 
162
sub0sub0 = Node("sub0sub0", parent=sub0)
163
sub0sub1 = Node("sub0sub1", parent=sub0)
164

165
# Group iteration - one tuple per level
166
for level_nodes in LevelOrderGroupIter(root):
167
    names = [node.name for node in level_nodes]
168
    print(f"Level: {names}")
169
# Output:
170
# Level: ['root']
171
# Level: ['sub0', 'sub1'] 
172
# Level: ['sub0sub0', 'sub0sub1']
173

174
# Useful for level-based processing
175
for depth, level_nodes in enumerate(LevelOrderGroupIter(root)):
176
    print(f"Processing {len(level_nodes)} nodes at depth {depth}")
177
```
178

179
### ZigZagGroupIter - ZigZag Level-order
180

181
Iterates over tree using level-order strategy with alternating left-to-right and right-to-left direction for each level. Returns groups like LevelOrderGroupIter but alternates direction.
182

183
```python { .api }
184
class ZigZagGroupIter(AbstractIter):
185
    """
186
    ZigZag level-order iteration returning groups (alternating direction).
187
    
188
    Args:
189
        node: Starting node for iteration
190
        filter_: Function called with every node as argument, node is returned if True
191
        stop: Stop iteration at node if stop function returns True for node
192
        maxlevel: Maximum descending in the node hierarchy
193
    """
194
    def __init__(self, node, filter_=None, stop=None, maxlevel=None): ...
195
```
196

197
**Usage Example:**
198

199
```python
200
from anytree import Node, ZigZagGroupIter
201

202
root = Node("root")
203
sub0 = Node("sub0", parent=root)
204
sub1 = Node("sub1", parent=root)
205
sub2 = Node("sub2", parent=root)
206
sub0sub0 = Node("sub0sub0", parent=sub0)
207
sub0sub1 = Node("sub0sub1", parent=sub0)
208
sub1sub0 = Node("sub1sub0", parent=sub1)
209

210
# ZigZag iteration - alternating direction per level
211
for level_nodes in ZigZagGroupIter(root):
212
    names = [node.name for node in level_nodes]
213
    print(f"Level: {names}")
214
# Output:
215
# Level: ['root']
216
# Level: ['sub0', 'sub1', 'sub2'] (left-to-right)
217
# Level: ['sub1sub0', 'sub0sub1', 'sub0sub0'] (right-to-left)
218
```
219

220
### AbstractIter - Base Iterator Class
221

222
Base class for all tree iterators. Provides common functionality and interface for custom iteration strategies.
223

224
```python { .api }
225
class AbstractIter:
226
    """
227
    Base class for tree iteration.
228
    """
229
    def __init__(self, node, filter_=None, stop=None, maxlevel=None): ...
230
    
231
    def __iter__(self): ...
232
    def __next__(self): ...
233
```
234

235
## Common Filtering Patterns
236

237
### Filter Functions
238

239
All iterators support filter functions for selective traversal:
240

241
```python
242
from anytree import Node, PreOrderIter
243

244
root = Node("root")
245
Node("file.txt", parent=root, type="file")  
246
Node("doc.pdf", parent=root, type="file")
247
Node("subdir", parent=root, type="directory")
248

249
# Filter by attribute
250
files_only = PreOrderIter(root, filter_=lambda n: getattr(n, 'type', None) == 'file')
251
for node in files_only:
252
    print(node.name)
253

254
# Filter by name pattern  
255
txt_files = PreOrderIter(root, filter_=lambda n: n.name.endswith('.txt'))
256
for node in txt_files:
257
    print(node.name)
258

259
# Filter by depth
260
shallow_nodes = PreOrderIter(root, filter_=lambda n: n.depth <= 2)
261
```
262

263
### Stop Functions
264

265
Control iteration termination with stop functions:
266

267
```python
268
from anytree import Node, PreOrderIter
269

270
root = Node("root")
271
private_dir = Node("private", parent=root)
272
Node("secret.txt", parent=private_dir)
273
public_dir = Node("public", parent=root)
274
Node("readme.txt", parent=public_dir)
275

276
# Stop at private directories
277
public_only = PreOrderIter(root, stop=lambda n: n.name == 'private')
278
for node in public_only:
279
    print(node.name)
280
# Output: root, public, readme.txt (skips private subtree)
281

282
# Stop when reaching max file count
283
file_count = 0
284
def stop_at_limit(node):
285
    global file_count
286
    if hasattr(node, 'type') and node.type == 'file':
287
        file_count += 1
288
    return file_count >= 3
289

290
limited_iter = PreOrderIter(root, stop=stop_at_limit)
291
```
292

293
### Level Limits
294

295
Control maximum traversal depth:
296

297
```python
298
from anytree import Node, PreOrderIter
299

300
# Create deep tree
301
root = Node("level0")
302
current = root
303
for i in range(1, 6):
304
    current = Node(f"level{i}", parent=current)
305

306
# Limit to first 3 levels
307
for node in PreOrderIter(root, maxlevel=3):
308
    print(f"{'  ' * node.depth}{node.name}")
309
# Output includes level0, level1, level2 only
310
```
311

312
## Performance Considerations
313

314
### Iterator Choice Guidelines
315

316
- **PreOrderIter**: Best for depth-first processing, tree serialization
317
- **PostOrderIter**: Best for bottom-up calculations, tree deletion
318
- **LevelOrderIter**: Best for breadth-first analysis, finding shortest paths
319
- **LevelOrderGroupIter**: Best for level-based batch processing
320
- **ZigZagGroupIter**: Best for balanced tree processing, visualization
321

322
### Memory Usage
323

324
All iterators are lazy and memory-efficient, yielding nodes on-demand rather than creating lists. For very large trees, prefer iterators over collecting results into lists:
325

326
```python
327
# Memory efficient - processes one node at a time
328
for node in PreOrderIter(huge_tree):
329
    process_node(node)
330

331
# Memory intensive - creates full list
332
all_nodes = list(PreOrderIter(huge_tree))  # Avoid for large trees
333
```