# How to Perform Depth-First Search (DFS) Traversal in treelib: A Complete Guide

> Learn to perform Depth-First Search DFS traversal in treelib. Use Tree.expand_tree() with mode=Tree.DEPTH for pre-order node sequences. Master treelib DFS today.

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

---

**Use `Tree.expand_tree()` with `mode=Tree.DEPTH` (or rely on the default) to yield node identifiers in pre-order DFS sequence.**

The `treelib` library provides a lightweight Python implementation for general-purpose tree data structures. When you need to visit every node in a tree by diving deep into branches before exploring siblings, the `Tree` class in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py) offers a built-in generator that handles Depth-First Search (DFS) traversal efficiently.

## Understanding DFS Architecture in treelib

### The Tree Class and Traversal Constants

In [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py), the `Tree` class defines four traversal mode constants at line 135:

| Constant | Value | Description |
|----------|-------|-------------|
| `Tree.ROOT` | 0 | Root node only |
| `Tree.DEPTH` | 1 | **Depth-first search** (pre-order) |
| `Tree.WIDTH` | 2 | Breadth-first search (level-order) |
| `Tree.ZIGZAG` | 3 | Alternating left-right per level |

When performing DFS traversal in treelib, you reference `Tree.DEPTH` to explicitly request depth-first behavior.

### How expand_tree Implements DFS

The core traversal logic resides in `Tree.expand_tree()` starting at line 929 in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py). This method is a **generator** that yields node identifiers (strings) according to the specified mode.

When `mode=Tree.DEPTH` (or when no mode is specified, since `DEPTH` is the default), the implementation uses a queue-based approach that simulates recursion:

1. It initializes an `expansion` list with the starting node (defaulting to the tree root)
2. For each iteration, it pops the first element and yields its identifier
3. It retrieves the node's children via `tree.children(nid)`
4. It concatenates these children **in front of** the remaining queue: `queue = expansion + queue[1:]`

This prepending operation at line 1047 produces a **pre-order DFS** traversal—visiting a node before its children, and exploring the first child deeply before moving to siblings.

## Performing DFS Traversal

### Basic DFS Using the Default Iterator

Since `Tree.DEPTH` is the default mode for `expand_tree()`, you can perform DFS traversal with minimal code:

```python
from treelib import Tree

# Construct a sample tree

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

# DFS traversal (pre-order) - default behavior

print("DFS traversal order:")
for node_id in tree.expand_tree():
    node = tree[node_id]
    print(f"  {node_id}: {node.tag}")

```

**Output:**

```

DFS traversal order:
  root: Root
  a: A
  c: C
  d: D
  b: B
  e: E

```

The generator yields identifiers in pre-order DFS sequence: root, then A and its descendants (C, D), then B and its descendant (E).

### Explicit DFS Mode Selection

For code clarity, explicitly pass `Tree.DEPTH` to `expand_tree()`:

```python

# Explicit DFS mode

for node_id in tree.expand_tree(mode=Tree.DEPTH):
    print(tree[node_id].tag)

```

This produces identical output to the default call but documents the traversal strategy for future maintainers.

### Manual Recursive DFS

When you need custom state tracking or post-order processing, implement recursive DFS using `Tree.children()`:

```python
def dfs_recursive(tree, node_id, visit_callback):
    """
    Perform recursive DFS on treelib Tree.
    visit_callback receives the Node object.
    """
    node = tree[node_id]
    visit_callback(node)  # Pre-order visit

    
    # Recurse on children (returns list of Node objects)

    for child in tree.children(node_id):
        dfs_recursive(tree, child.identifier, visit_callback)

# Usage

def print_node(node):
    indent = "  " * tree.level(node.identifier)
    print(f"{indent}{node.tag}")

dfs_recursive(tree, tree.root, print_node)

```

This approach gives you full control over the traversal stack and enables post-order or in-order variations by moving the `visit_callback` invocation.

## Practical Applications

### Calculating Tree Depth

Combine DFS traversal with `Tree.depth()` to analyze tree structure. The `depth()` method at line 778 in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py) computes either the maximum depth of the entire tree or the level of a specific node:

```python

# Maximum depth from root to deepest leaf

max_depth = tree.depth()
print(f"Tree depth: {max_depth}")

# Level of specific node (distance from root)

level_of_c = tree.depth("c")
print(f"Node 'c' is at level: {level_of_c}")

```

### Processing Nodes with Custom Logic

DFS traversal enables tree reduction operations, such as summing values stored in node data:

```python

# Assume nodes have numeric data

tree = Tree()
tree.create_node("Root", "root", data=10)
tree.create_node("Child1", "c1", parent="root", data=5)
tree.create_node("Child2", "c2", parent="root", data=3)

total = 0
for nid in tree.expand_tree():
    node = tree[nid]
    if node.data:
        total += node.data

print(f"Sum of all node data: {total}")  # Output: 18

```

## Summary

- **`Tree.expand_tree()`** is the primary method for DFS traversal in treelib, defaulting to `Tree.DEPTH` mode for pre-order depth-first search.
- The implementation in [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py) uses a queue-based generator that prepends children to the expansion list, yielding identifiers in root-left-right sequence.
- Access actual **Node** objects by indexing the tree with the identifier: `tree[node_id]`.
- For custom traversal logic, use **`Tree.children()`** to retrieve child nodes and implement recursive DFS manually.
- Combine traversal with **`Tree.depth()`** to analyze tree levels and structure.

## Frequently Asked Questions

### What is the default traversal mode in treelib?

By default, `Tree.expand_tree()` uses `Tree.DEPTH` (value 1), which performs a pre-order depth-first search. This means it visits the root node, then recursively explores each branch fully before moving to the next sibling. You can verify this in the method signature at line 929 of [`treelib/tree.py`](https://github.com/caesar0301/treelib/blob/main/treelib/tree.py).

### How do I perform post-order DFS traversal in treelib?

The built-in `expand_tree()` only supports pre-order DFS. For post-order traversal (children before parent), implement a recursive function using `Tree.children()`. Process all children recursively before visiting the current node, as shown in the manual recursive DFS example above.

### Can I limit DFS traversal to a specific subtree?

Yes. Pass the `nid` parameter to `expand_tree()` to specify the starting node identifier. For example, `tree.expand_tree(nid="a")` performs DFS starting from node "a" rather than the tree root. This is useful for processing specific branches without traversing the entire tree.

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

`Tree.DEPTH` (value 1) performs depth-first search, exploring as far as possible along each branch before backtracking. `Tree.WIDTH` (value 2) performs breadth-first search, visiting all nodes at the current level before moving to the next level. Both modes are available in `expand_tree()` via the `mode` parameter.