# Internal Architecture of tree_regions_system: Queue-Based Region Detection in BetterHTMLChunking

> Discover the internal architecture of the tree_regions_system in betterhtmlchunking. Learn how queue-based processing partitions HTML documents efficiently while preserving order.

- Repository: [Carlos A. Planchón/betterhtmlchunking](https://github.com/carlosplanchon/betterhtmlchunking)
- Tags: internals
- Published: 2026-02-26

---

**The `tree_regions_system` module in `carlosplanchon/betterhtmlchunking` uses a breadth-first queue traversal to partition HTML documents into size-constrained Regions of Interest (ROIs), deferring oversized nodes for deeper processing while preserving document order.**

The `tree_regions_system` is the core engine of the `carlosplanchon/betterhtmlchunking` repository responsible for intelligently chunking HTML documents. By implementing a **queue-based processing architecture**, it transforms a hierarchical DOM tree into flat, manageable regions that respect maximum length constraints without breaking document semantics.

## Three-Layer Architecture of tree_regions_system

The internal design separates concerns across three distinct layers that work together to process HTML documents:

| Layer | Responsibility | Main Types / Functions |
|-------|----------------|------------------------|
| **Tree representation** | Parses raw HTML, builds a `treelib.Tree` where each node stores text and HTML lengths. | `DOMTreeRepresentation` (see [`betterhtmlchunking/tree_representation.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_representation.py)) |
| **ROI construction** | Given a node and its direct children, groups children into chunks that do not exceed `max_node_repr_length`. Handles oversized children by enqueuing them for deeper processing. | `ROIMaker`, `RegionOfInterest` (see [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py) lines 57-89) |
| **Queue-driven traversal** | Performs a breadth-first walk over the tree, repeatedly invoking `ROIMaker`. The queue ensures that large sub-trees are revisited after their parent has been processed. | `TreeRegionsSystem.start()` (see [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py) lines 42-68) |

## Queue-Based Breadth-First Traversal

The `TreeRegionsSystem` class implements the main processing loop using Python's `queue.Queue` to manage nodes awaiting inspection. This approach avoids deep recursion and ensures predictable memory usage when processing deeply nested HTML documents.

The system initializes the queue with a root xpath (either explicitly supplied, `/html`, or the first xpath in the representation):

```python
subtrees_queue = queue.Queue()
subtrees_queue.put(root_xpath)

```

A classic while-loop dequeues one xpath at a time, processes the node, gathers its children, and may push additional child xpaths back onto the queue:

```python
while not subtrees_queue.empty():
    node_xpath = subtrees_queue.get()
    # …process node…

    for child_tag in region_of_interest_maker.children_to_enqueue:
        subtrees_queue.put(child_tag)

```

**Why a queue?** Breadth-first order preserves document order for the final ROI list, and it allows the algorithm to postpone processing of oversized children until the parent's ROI has been emitted. This avoids deep-recursive calls and keeps memory usage predictable when handling complex DOM structures.

## ROI Creation with ROIMaker

For each dequeued node, the system instantiates an `ROIMaker` that groups direct children into `RegionOfInterest` objects respecting the `max_node_repr_length` constraint.

The `ROIMaker._process_children` method (lines 14-21 in [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py)) walks the child list, accumulating their representation length:

```python
node_length = self.get_node_repr_length(node)

```

Whenever the accumulated length would exceed the budget, the current `RegionOfInterest` is closed and a new one started. If a single child alone exceeds the budget, that child is **not** placed in any region; instead it is appended to `self.children_to_enqueue` so that it will be processed as a new root later.

When a node has **no children** or **all children fit into a single region**, `_check_node_as_roi` collapses the whole node into a single ROI, marking it with `node_is_roi = True` (lines 46-57 in [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py)).

## Collecting and Ordering Final Regions

All ROIs produced by each `ROIMaker` instance are appended to `self.regions_of_interest_list`. After the queue is empty, the list is sorted by document order using the helper `order_regions_of_interest_by_pos_xpath`, which leverages the original `pos_xpaths_list` from the representation to compute a deterministic order (lines 71-89 in [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py)).

If no ROI satisfies the size constraint, the algorithm falls back to a single ROI that covers the whole document (lines 150-170 in [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py)).

The final sorted mapping (`self.sorted_roi_by_pos_xpath`) is stored as an indexed dictionary for easy downstream consumption.

## Practical Usage Examples

### Basic ROI Extraction

```python
from betterhtmlchunking.tree_representation import DOMTreeRepresentation
from betterhtmlchunking.tree_regions_system import TreeRegionsSystem

# Load raw HTML

html = """<html><body>
    <p>First paragraph.</p>
    <p>Second paragraph with <img src="a.png"/> a picture.</p>
    <div>Some <span>nested</span> content.</div>
</body></html>"""

# Build tree representation

tree_repr = DOMTreeRepresentation(website_code=html)

# Create regions system with a 200-character budget (HTML length)

regions = TreeRegionsSystem(
    tree_representation=tree_repr,
    max_node_repr_length=200,
    repr_length_compared_by="html_length"
)

# Retrieve ordered ROIs

for idx, roi in regions.sorted_roi_by_pos_xpath.items():
    print(f"ROI #{idx+1}:")
    print("  XPaths :", roi.pos_xpath_list)
    print("  Length :", roi.repr_length)
    print("  Whole node ROI ?", roi.node_is_roi)

```

### Adjusting Budget Constraints

```python

# Use a stricter budget of 100 characters based on text length

regions_small = TreeRegionsSystem(
    tree_representation=tree_repr,
    max_node_repr_length=100,
    repr_length_compared_by="text_length"
)

# The queue will now enqueue many deeper nodes, producing finer-grained chunks

print("Number of ROIs:", len(regions_small.sorted_roi_by_pos_xpath))

```

These examples demonstrate the three-step workflow: **(1) parse → (2) queue-driven ROI generation → (3) ordered output**.

## Summary

- **`TreeRegionsSystem`** implements a **queue-based breadth-first traversal** using `queue.Queue` to process HTML documents iteratively rather than recursively.
- The architecture separates concerns into three layers: **tree representation** (`DOMTreeRepresentation`), **ROI construction** (`ROIMaker`), and **queue-driven traversal** (`TreeRegionsSystem`).
- **Oversized nodes** are deferred via `children_to_enqueue`, allowing the system to break large DOM subtrees into smaller chunks without breaking document order.
- Final regions are **sorted by document position** using `order_regions_of_interest_by_pos_xpath` to ensure deterministic, sequential output.
- The implementation resides primarily in [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py) with supporting types in [`betterhtmlchunking/tree_representation.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_representation.py).

## Frequently Asked Questions

### How does tree_regions_system handle deeply nested HTML documents without recursion?

The `tree_regions_system` avoids Python's recursion limit by using a `queue.Queue` to manage nodes awaiting processing. When `TreeRegionsSystem.start()` encounters a child that exceeds `max_node_repr_length`, it appends that child to `children_to_enqueue` rather than recursing. After the current node's regions are emitted, these children are added to the queue for subsequent iteration. This breadth-first approach keeps memory usage predictable and prevents stack overflow errors on deeply nested DOM structures.

### What is the difference between text_length and html_length in the queue processing?

The `repr_length_compared_by` parameter determines which metric `ROIMaker` uses to calculate node sizes during queue processing. When set to `"text_length"`, the system measures only the visible text content of nodes, ignoring HTML tags and attributes. When set to `"html_length"`, it counts the full HTML serialization including tags, attributes, and whitespace. This choice affects which nodes get enqueued for deeper processing: a node with heavy HTML markup but little text might exceed the budget under `html_length` but pass under `text_length`, triggering different queue traversal patterns.

### How does the system ensure regions are returned in document order?

After the queue empties, `TreeRegionsSystem` calls `order_regions_of_interest_by_pos_xpath` (lines 71-89 in [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py)) to sort the collected regions. This function uses the original `pos_xpaths_list` from `DOMTreeRepresentation`, which maps each xpath to its document position index. By comparing these indices, the system produces a deterministic ordering that matches the original HTML document sequence, even though the breadth-first queue processing might have generated regions in a different temporal order.

### What happens when no regions satisfy the size constraint?

If the queue processing completes without producing any valid regions (for example, when the entire document exceeds `max_node_repr_length` and cannot be split further), the system implements a fallback mechanism in lines 150-170 of [`betterhtmlchunking/tree_regions_system.py`](https://github.com/carlosplanchon/betterhtmlchunking/blob/main/betterhtmlchunking/tree_regions_system.py). It creates a single `RegionOfInterest` covering the entire document tree, ensuring that the caller always receives at least one region even when the chunking constraints cannot be strictly satisfied. This prevents empty results and ensures downstream consumers always have content to process.