Tree Traversal Modes in treelib: Depth-First, Breadth-First, and Zigzag Explained

The treelib library supports three tree traversal modes—depth-first (DEPTH), breadth-first (WIDTH), and zigzag (ZIGZAG)—controlled via the mode parameter in the expand_tree() method.

The caesar0301/treelib library provides a Python implementation for managing tree data structures. Understanding the available tree traversal modes is essential for controlling how nodes are visited during iteration. The library defines three traversal constants in treelib/tree.py that determine the order in which expand_tree() yields nodes.

The Three Tree Traversal Constants in treelib

In treelib/tree.py (lines 101–106), the Tree class defines three integer constants that represent different traversal strategies:

• Tree.DEPTH (value 1): Implements depth-first search (DFS) in pre-order, visiting a node before its children. This is the default mode when calling expand_tree().
• Tree.WIDTH (value 2): Implements breadth-first search (BFS), visiting all nodes level by level using a queue-based approach.
• Tree.ZIGZAG (value 3): Implements a zigzag (or spiral) traversal that alternates the direction of breadth-first traversal on each level—left-to-right on the first level, right-to-left on the second, and so on.

These constants are passed to the mode parameter of the expand_tree() generator, as defined in the method signature at tree.py lines 48–52.

How expand_tree() Implements Tree Traversal Modes

The expand_tree() method in treelib/tree.py serves as the primary mechanism for iterating over tree nodes. According to the source code, the method signature accepts a mode argument that defaults to Tree.DEPTH:

def expand_tree(self, nid=None, mode=1, filter=None, key=None, reverse=False):

When invoked, the generator uses the specified mode to determine the algorithm for traversing the tree structure. Depth-first traversal recursively explores each branch to its full depth before backtracking. Breadth-first traversal uses a queue to process all siblings at the current depth before moving to the next level. The zigzag mode modifies the breadth-first approach by reversing the node order on alternating levels.

Practical Examples of Tree Traversal Modes

The following examples demonstrate how to use each traversal mode with a sample tree structure. This code is adapted from the official examples in examples/tree_algorithms.py:

from treelib import Tree

# Build a simple tree

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

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

# 1. Depth-first (default)

print("Depth-first order:")
for nid in t.expand_tree():          # mode defaults to Tree.DEPTH

    print(t[nid].tag, end=" → ")

# Output: A → B → D → C → E

# 2. Breadth-first

print("\nBreadth-first order:")
for nid in t.expand_tree(mode=Tree.WIDTH):
    print(t[nid].tag, end=" → ")

# Output: A → B → C → D → E

# 3. Zigzag

print("\nZigzag order:")
for nid in t.expand_tree(mode=Tree.ZIGZAG):
    print(t[nid].tag, end=" → ")

# Output: A → C → B → D → E

In the depth-first output, node D (child of B) is visited before node C (sibling of B). In breadth-first mode, all children of the root (B and C) are visited before their children (D and E). The zigzag mode visits C before B on the second level, demonstrating the alternating direction.

Summary

• treelib defines three traversal constants in treelib/tree.py: Tree.DEPTH (1), Tree.WIDTH (2), and Tree.ZIGZAG (3).
• The expand_tree() generator method accepts these constants via its mode parameter to control iteration order.
• Depth-first (default) visits nodes pre-order, exploring each branch completely before moving to siblings.
• Breadth-first processes nodes level by level, suitable for finding the shortest path to a target node.
• Zigzag traversal alternates direction per level, useful for specific visualization or processing patterns.
• Reference implementations are available in examples/tree_algorithms.py.

Frequently Asked Questions

What is the default tree traversal mode in treelib?

According to the source code in treelib/tree.py at line 48, the expand_tree() method defaults to mode=1, which corresponds to Tree.DEPTH. This implements a pre-order depth-first search where parent nodes are yielded before their children, and each branch is fully explored before moving to the next sibling.

How do I perform a level-order traversal using treelib?

To perform a level-order (breadth-first) traversal, pass Tree.WIDTH to the expand_tree() method. This constant (value 2) configures the generator to use a queue-based approach, visiting all nodes at the current depth before proceeding to the next level, as implemented in the tree traversal logic.

What is the difference between WIDTH and ZIGZAG traversal modes?

Both modes process nodes level by level, but WIDTH (breadth-first) consistently visits nodes from left to right at each level, while ZIGZAG alternates the direction—left-to-right on odd levels and right-to-left on even levels. This creates a spiral pattern useful for specific hierarchical data processing or display requirements.

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

The traversal constants DEPTH, WIDTH, and ZIGZAG are defined as class variables in treelib/tree.py at lines 101–106. These integer values (1, 2, and 3 respectively) are used by the expand_tree() method to select the appropriate traversal algorithm during tree iteration.

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