# How to Perform Breadth-First Search (BFS) Traversal in Treelib

> Learn how to perform Breadth-First Search BFS traversal in treelib using Tree.expand_tree(mode=Tree.WIDTH). Traverse nodes level by level efficiently with this simple method.

- Repository: [Xiaming Chen/treelib](https://github.com/caesar0301/treelib)
- Tags: how-to-guide
- Published: 2026-02-26

---

**Use `Tree.expand_tree(mode=Tree.WIDTH)` to execute Breadth-First Search in treelib, which traverses nodes level-by-level using an internal FIFO queue.**

Treelib provides a robust tree data structure implementation for Python, and performing Breadth-First Search (BFS) traversal requires only a single method call with a specific mode parameter. The library's traversal architecture is defined in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py), where the `expand_tree` generator handles multiple traversal algorithms including BFS through the `Tree.WIDTH` constant.

## Understanding the BFS Implementation

The core BFS functionality resides in the `expand_tree` method within [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py). This versatile generator accepts a `mode` argument that determines the traversal strategy, allowing you to switch between Depth-First Search (DFS) and Breadth-First Search seamlessly.

### Traversal Mode Constants

In [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py) (lines 135-139), treelib defines four traversal constants that control the iteration order:

| Constant | Value | Description |
|----------|-------|-------------|
| `Tree.ROOT` | 0 | Root-only traversal (internal use) |
| `Tree.DEPTH` | 1 | Depth-first search (DFS) — default behavior |
| `Tree.WIDTH` | 2 | **Breadth-first search (BFS)** |
| `Tree.ZIGZAG` | 3 | Alternating level traversal (zig-zag) |

When you pass `mode=Tree.WIDTH` to `expand_tree`, the method implements BFS using a **FIFO queue** (First-In-First-Out). The algorithm dequeues the current node identifier, yields it to the caller, then enqueues all children of that node. This guarantees that all nodes at depth *d* are visited before any node at depth *d + 1*, maintaining the canonical BFS order.

## Basic BFS Traversal Example

To perform a standard Breadth-First Search traversal, create a tree structure and iterate using `expand_tree` with the width mode:

```python
from treelib import Tree

# Build a sample tree

tree = Tree()
tree.create_node("A", "a")                 # root

tree.create_node("B", "b", parent="a")
tree.create_node("C", "c", parent="a")
tree.create_node("D", "d", parent="b")
tree.create_node("E", "e", parent="c")

# Execute BFS traversal

for nid in tree.expand_tree(mode=Tree.WIDTH):
    print(f"BFS: {tree[nid].tag}")

```

This outputs the nodes in strict level-order:

```

BFS: A
BFS: B
BFS: C
BFS: D
BFS: E

```

The example follows the implementation demonstrated in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py) (lines 982-985) and the getting started tutorial in [`examples/getting_started.py`](https://github.com/caesar0301/treelib/blob/main/examples/getting_started.py) (lines 157-160).

## Advanced BFS Techniques

The `expand_tree` method supports additional parameters that work seamlessly with BFS mode to control which nodes are visited and in what order.

### Filtering Nodes During Traversal

You can apply a filter function to perform selective BFS, visiting only nodes that meet specific criteria:

```python

# BFS with filter: only visit nodes with tags starting with vowels

vowel_filter = lambda node: node.tag[0].lower() in "aeiou"

for nid in tree.expand_tree(mode=Tree.WIDTH, filter=vowel_filter):
    print(f"Vowel node: {tree[nid].tag}")

```

This pattern appears in the library's demo scripts (lines 990-993 of [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py)) and allows you to traverse large trees efficiently while skipping irrelevant branches.

### Sorting and Key Functions

The method also accepts `key` and `sorting` parameters that determine the order of sibling nodes within each BFS level. When `sorting=True`, the `key` function (defaulting to `operator.attrgetter('tag')`) sorts children before they are enqueued, ensuring deterministic traversal order while maintaining breadth-first guarantees.

## Performance and Memory Considerations

Because `expand_tree` is a **generator**, it yields node identifiers lazily without materializing the entire traversal list in memory. This architecture allows BFS to handle arbitrarily large trees efficiently, as the queue only stores identifiers for the current frontier (nodes at the current and next depth levels).

The FIFO queue implementation ensures O(n) time complexity for visiting *n* nodes, with O(w) space complexity where *w* represents the maximum width of the tree (the number of nodes at the deepest level).

## Summary

- **Use `Tree.expand_tree(mode=Tree.WIDTH)`** to perform BFS traversal in treelib, as implemented in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py).
- The **FIFO queue** mechanism guarantees level-by-level visitation, with all nodes at depth *d* processed before depth *d + 1*.
- **Traversal constants** (`Tree.DEPTH`, `Tree.WIDTH`, `Tree.ZIGZAG`) are defined at lines 135-139 in the source code.
- The **generator pattern** enables memory-efficient traversal of large trees without loading all nodes into memory simultaneously.
- **Filter and sort parameters** allow selective BFS traversal while preserving breadth-first ordering guarantees.

## Frequently Asked Questions

### What is the difference between Tree.DEPTH and Tree.WIDTH in treelib?

`Tree.DEPTH` (value 1) performs Depth-First Search (DFS), which explores as far as possible along each branch before backtracking. `Tree.WIDTH` (value 2) performs Breadth-First Search (BFS), which explores all neighbors at the present depth prior to moving to nodes at the next depth level. Both modes use the same `expand_tree` method but implement different queueing strategies internally.

### Can I use BFS traversal with filtered nodes in treelib?

Yes, pass a `filter` callable to `expand_tree(mode=Tree.WIDTH)`. The filter receives each `Node` object and should return `True` to visit the node or `False` to skip it. The BFS order is maintained for all nodes that pass the filter condition, allowing you to perform level-order searches on subtrees or specific node types.

### How does treelib handle memory for large tree traversals?

Treelib uses a generator-based implementation for `expand_tree`, yielding one node identifier at a time rather than returning a complete list. This lazy evaluation means BFS traversal consumes O(w) memory (where w is the tree's maximum width) rather than O(n), making it suitable for processing very large trees that cannot fit entirely in memory.

### Where are the traversal constants defined in the treelib source code?

The traversal mode constants (`Tree.ROOT`, `Tree.DEPTH`, `Tree.WIDTH`, and `Tree.ZIGZAG`) are defined in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py) at lines 135-139. These integer constants control the behavior of the `expand_tree` method, with `Tree.WIDTH` specifically enabling the FIFO queue mechanism required for Breadth-First Search.