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

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, 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. 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 (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:

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 (lines 982-985) and the getting started tutorial in 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:

# 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) 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.
• 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 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}