0
# Tree Traversal
1

2
TreeSwift provides comprehensive tree traversal methods implemented as memory-efficient generators. All traversal methods support filtering by node type (leaves, internal nodes, or both) and provide flexible iteration patterns for different algorithmic needs.
3

4
## Capabilities
5

6
### Preorder Traversal
7

8
Visits nodes in preorder: current node first, then recursively visit children. Useful for top-down tree processing and copying operations.
9

10
```python { .api }
11
def traverse_preorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
12
    """
13
    Perform preorder traversal starting at this node.
14

15
    Parameters:
16
    - leaves (bool): Include leaf nodes in traversal
17
    - internal (bool): Include internal nodes in traversal
18

19
    Yields:
20
    - Node: Nodes in preorder sequence
21
    """
22
```
23

24
Usage examples:
25

26
```python
27
import treeswift
28

29
tree = treeswift.read_tree_newick("((A,B),(C,D));")
30

31
# Traverse all nodes in preorder
32
for node in tree.traverse_preorder():
33
    print(f"Node: {node.get_label()}, is_leaf: {node.is_leaf()}")
34

35
# Traverse only leaves
36
for leaf in tree.traverse_preorder(internal=False):
37
    print(f"Leaf: {leaf.get_label()}")
38

39
# Traverse only internal nodes
40
for internal_node in tree.traverse_preorder(leaves=False):
41
    print(f"Internal node with {internal_node.num_children()} children")
42
```
43

44
### Postorder Traversal
45

46
Visits children first, then the current node. Essential for bottom-up computations like calculating subtree statistics.
47

48
```python { .api }
49
def traverse_postorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
50
    """
51
    Perform postorder traversal starting at this node.
52

53
    Parameters:
54
    - leaves (bool): Include leaf nodes in traversal
55
    - internal (bool): Include internal nodes in traversal
56

57
    Yields:
58
    - Node: Nodes in postorder sequence
59
    """
60
```
61

62
Usage examples:
63

64
```python
65
import treeswift
66

67
tree = treeswift.read_tree_newick("((A:0.1,B:0.2):0.5,(C:0.3,D:0.4):0.6):0.0;")
68

69
# Calculate subtree sums in postorder
70
subtree_sums = {}
71
for node in tree.traverse_postorder():
72
    if node.is_leaf():
73
        subtree_sums[node] = node.get_edge_length() or 0
74
    else:
75
        subtree_sums[node] = sum(subtree_sums[child] for child in node.children)
76
        if node.get_edge_length():
77
            subtree_sums[node] += node.get_edge_length()
78

79
print(f"Total tree length: {subtree_sums[tree.root]}")
80
```
81

82
### Level-order Traversal
83

84
Visits nodes level by level (breadth-first), useful for level-based algorithms and visualization.
85

86
```python { .api }
87
def traverse_levelorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
88
    """
89
    Perform level-order (breadth-first) traversal starting at this node.
90

91
    Parameters:
92
    - leaves (bool): Include leaf nodes in traversal
93
    - internal (bool): Include internal nodes in traversal
94

95
    Yields:
96
    - Node: Nodes in level-order sequence
97
    """
98
```
99

100
Usage examples:
101

102
```python
103
import treeswift
104

105
tree = treeswift.read_tree_newick("(((A,B),C),((D,E),F));")
106

107
# Print tree structure level by level
108
current_level = 0
109
nodes_at_level = []
110

111
for node in tree.traverse_levelorder():
112
    # Calculate node depth
113
    depth = 0
114
    curr = node
115
    while curr.parent is not None:
116
        depth += 1
117
        curr = curr.parent
118
    
119
    if depth > current_level:
120
        if nodes_at_level:
121
            print(f"Level {current_level}: {[n.get_label() or 'internal' for n in nodes_at_level]}")
122
        current_level = depth
123
        nodes_at_level = []
124
    
125
    nodes_at_level.append(node)
126

127
if nodes_at_level:
128
    print(f"Level {current_level}: {[n.get_label() or 'internal' for n in nodes_at_level]}")
129
```
130

131
### Inorder Traversal
132

133
For binary trees, visits left subtree, current node, then right subtree. Raises error for non-binary trees.
134

135
```python { .api }
136
def traverse_inorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
137
    """
138
    Perform inorder traversal starting at this node (binary trees only).
139

140
    Parameters:
141
    - leaves (bool): Include leaf nodes in traversal
142
    - internal (bool): Include internal nodes in traversal
143

144
    Yields:
145
    - Node: Nodes in inorder sequence
146

147
    Raises:
148
    - RuntimeError: If tree contains non-binary nodes
149
    """
150
```
151

152
Usage examples:
153

154
```python
155
import treeswift
156

157
# Binary tree
158
tree = treeswift.read_tree_newick("((A,B),(C,D));")
159

160
try:
161
    for node in tree.traverse_inorder():
162
        print(f"Node: {node.get_label() or 'internal'}")
163
except RuntimeError as e:
164
    print(f"Error: {e}")
165

166
# This will raise an error (non-binary)
167
try:
168
    tree = treeswift.read_tree_newick("(A,B,C);")
169
    for node in tree.traverse_inorder():
170
        print(node)
171
except RuntimeError as e:
172
    print(f"Cannot perform inorder on non-binary tree: {e}")
173
```
174

175
### Root Distance Order Traversal
176

177
Visits nodes ordered by their distance from the root, either ascending or descending.
178

179
```python { .api }
180
def traverse_rootdistorder(self, ascending: bool = True, leaves: bool = True, internal: bool = True) -> Generator[tuple[float, Node], None, None]:
181
    """
182
    Traverse nodes ordered by distance from root.
183

184
    Parameters:
185
    - ascending (bool): True for ascending distance order, False for descending
186
    - leaves (bool): Include leaf nodes in traversal
187
    - internal (bool): Include internal nodes in traversal
188

189
    Yields:
190
    - tuple[float, Node]: (distance_from_root, node) pairs in distance order
191
    """
192
```
193

194
Usage examples:
195

196
```python
197
import treeswift
198

199
tree = treeswift.read_tree_newick("((A:0.1,B:0.2):0.3,(C:0.4,D:0.5):0.6):0.0;")
200

201
# Nodes by increasing distance from root
202
print("Nodes by distance from root (ascending):")
203
for distance, node in tree.traverse_rootdistorder(ascending=True):
204
    label = node.get_label() or "internal"
205
    print(f"  {distance:.1f}: {label}")
206

207
# Nodes by decreasing distance from root (leaves first)
208
print("\nNodes by distance from root (descending):")
209
for distance, node in tree.traverse_rootdistorder(ascending=False):
210
    label = node.get_label() or "internal"
211
    print(f"  {distance:.1f}: {label}")
212

213
# Only leaves by distance
214
print("\nLeaves by distance from root:")
215
for distance, node in tree.traverse_rootdistorder(internal=False):
216
    print(f"  {distance:.1f}: {node.get_label()}")
217
```
218

219
### Specialized Traversal Methods
220

221
Convenience methods for specific node types.
222

223
```python { .api }
224
def traverse_leaves(self) -> Generator[Node, None, None]:
225
    """Traverse only leaf nodes (convenience method)."""
226

227
def traverse_internal(self) -> Generator[Node, None, None]:
228
    """Traverse only internal nodes (convenience method)."""
229
```
230

231
Usage examples:
232

233
```python
234
import treeswift
235

236
tree = treeswift.read_tree_newick("((A,B),(C,D));")
237

238
# Get all leaf labels
239
leaf_labels = [node.get_label() for node in tree.traverse_leaves()]
240
print(f"Leaves: {leaf_labels}")
241

242
# Count internal nodes
243
internal_count = sum(1 for node in tree.traverse_internal())
244
print(f"Internal nodes: {internal_count}")
245
```
246

247
### Node-level Traversal Methods
248

249
Individual nodes also support traversal methods for subtree operations.
250

251
```python { .api }
252
# Node class methods
253
def traverse_preorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
254
    """Preorder traversal starting from this node."""
255

256
def traverse_postorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
257
    """Postorder traversal starting from this node."""
258

259
def traverse_levelorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
260
    """Level-order traversal starting from this node."""
261

262
def traverse_ancestors(self, include_self: bool = True) -> Generator[Node, None, None]:
263
    """Traverse ancestors of this node toward root."""
264

265
def traverse_bfs(self, include_self: bool = True) -> Generator[tuple[Node, float], None, None]:
266
    """Breadth-first search yielding (node, distance) pairs."""
267
```
268

269
Usage examples:
270

271
```python
272
import treeswift
273

274
tree = treeswift.read_tree_newick("(((A,B),C),((D,E),F));")
275

276
# Find a specific leaf and traverse its ancestors
277
for node in tree.traverse_leaves():
278
    if node.get_label() == "A":
279
        print("Ancestors of A:")
280
        for ancestor in node.traverse_ancestors():
281
            label = ancestor.get_label() or f"internal({ancestor.num_children()} children)"
282
            print(f"  {label}")
283
        break
284

285
# BFS from a specific internal node
286
internal_nodes = list(tree.traverse_internal())
287
if internal_nodes:
288
    start_node = internal_nodes[0]
289
    print(f"\nBFS from internal node:")
290
    for node, distance in start_node.traverse_bfs():
291
        label = node.get_label() or "internal"
292
        print(f"  Distance {distance}: {label}")
293
```