tessl/pypi-treelib

A Python implementation of tree data structure with hierarchical organization and efficient operations for traversal, modification, search, and visualization.

Overview

Eval results

Files

Tree Traversal and Navigation

Name: tessl/pypi-treelib
Author: tessl

Comprehensive functionality for navigating and traversing tree structures using multiple algorithms including depth-first, breadth-first, and zigzag patterns. Provides efficient iteration, filtering, and path-finding capabilities.

Capabilities

Tree Traversal

Navigate trees using different traversal algorithms with customizable filtering and sorting.

def expand_tree(nid=None, mode=DEPTH, filter=None, key=None, reverse=False, sorting=True) -> Iterator[str]:
    """
    Traverse tree nodes in specified order yielding node identifiers.
    
    Parameters:
    - nid: str, starting node identifier (default: root)
    - mode: int, traversal mode (DEPTH, WIDTH, ZIGZAG)
    - filter: callable, function to filter nodes (node) -> bool
    - key: callable, function for sorting nodes (node) -> comparable
    - reverse: bool, reverse sort order
    - sorting: bool, enable/disable sorting
    
    Returns:
    Iterator[str], node identifiers in traversal order
    """

def rsearch(nid, filter=None) -> Iterator[str]:
    """
    Traverse from node to root (reverse search).
    
    Parameters:
    - nid: str, starting node identifier
    - filter: callable, function to filter nodes (node) -> bool
    
    Returns:
    Iterator[str], node identifiers from node to root
    """

Usage Examples:

# Depth-first traversal (default)
for node_id in tree.expand_tree():
    print(f"Visiting: {tree[node_id].tag}")

# Breadth-first traversal
for node_id in tree.expand_tree(mode=Tree.WIDTH):
    level = tree.level(node_id)
    print(f"Level {level}: {tree[node_id].tag}")

# Zigzag traversal
for node_id in tree.expand_tree(mode=Tree.ZIGZAG):
    print(f"Zigzag order: {tree[node_id].tag}")

# Start from specific node
for node_id in tree.expand_tree(nid="engineering"):
    print(f"Subtree: {tree[node_id].tag}")

# With filtering and sorting
for node_id in tree.expand_tree(
    filter=lambda node: node.is_leaf(tree.identifier),
    key=lambda node: node.tag,
    reverse=True
):
    print(f"Leaf (sorted): {tree[node_id].tag}")

# Path from node to root
for ancestor_id in tree.rsearch("employee_1"):
    print(f"Ancestor: {tree[ancestor_id].tag}")

Structure Queries

Query tree structure and relationships between nodes.

def children(nid) -> list[Node]:
    """
    Get direct children of a node.
    
    Parameters:
    - nid: str, parent node identifier
    
    Returns:
    list[Node], list of child Node objects
    """

def is_branch(nid) -> list[str]:
    """
    Get child node identifiers.
    
    Parameters:
    - nid: str, parent node identifier
    
    Returns:
    list[str], list of child node identifiers
    """

def parent(nid) -> Node | None:
    """
    Get parent node object.
    
    Parameters:
    - nid: str, child node identifier
    
    Returns:
    Node object or None if root/not found
    """

def siblings(nid) -> list[Node]:
    """
    Get sibling nodes (nodes with same parent).
    
    Parameters:
    - nid: str, node identifier
    
    Returns:
    list[Node], list of sibling Node objects
    """

def leaves(nid=None) -> list[Node]:
    """
    Get all leaf nodes (nodes with no children).
    
    Parameters:
    - nid: str, subtree root (default: entire tree)
    
    Returns:
    list[Node], list of leaf Node objects
    """

Usage Examples:

# Get children
engineering_team = tree.children("engineering")
for member in engineering_team:
    print(f"Team member: {member.tag}")

# Get child identifiers
child_ids = tree.is_branch("engineering")
print(f"Child IDs: {child_ids}")

# Get parent
manager = tree.parent("alice")
if manager:
    print(f"Alice's manager: {manager.tag}")

# Get siblings
coworkers = tree.siblings("alice")
for coworker in coworkers:
    print(f"Coworker: {coworker.tag}")

# Get all leaf nodes
leaves = tree.leaves()
individual_contributors = [leaf.tag for leaf in leaves]
print(f"Individual contributors: {individual_contributors}")

# Get leaves in subtree
eng_leaves = tree.leaves("engineering")

Tree Metrics and Analysis

Analyze tree structure and compute various metrics.

def size(level=None) -> int:
    """
    Get number of nodes in tree or at specific level.
    
    Parameters:
    - level: int, specific level to count (optional)
    
    Returns:
    int, number of nodes
    """

def depth(node=None) -> int:
    """
    Get maximum depth of tree or depth of specific node.
    
    Parameters:
    - node: Node object or str, specific node (optional)
    
    Returns:
    int, depth value
    """

def level(nid, filter=None) -> int:
    """
    Get level/depth of specific node.
    
    Parameters:
    - nid: str, node identifier
    - filter: callable, filtering function (optional)
    
    Returns:
    int, level/depth of node (root is level 0)
    """

Usage Examples:

# Total tree size
total_nodes = tree.size()
print(f"Total employees: {total_nodes}")

# Size at specific level
managers = tree.size(level=1)
print(f"Number of managers: {managers}")

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

# Node level
alice_level = tree.level("alice")
print(f"Alice is at level: {alice_level}")

# Depth from specific node
subtree_depth = tree.depth(tree["engineering"])
print(f"Engineering dept depth: {subtree_depth}")

Relationship Analysis

Analyze relationships and ancestry between nodes.

def is_ancestor(ancestor, grandchild) -> bool:
    """
    Check if one node is ancestor of another.
    
    Parameters:
    - ancestor: str, potential ancestor node identifier
    - grandchild: str, potential descendant node identifier
    
    Returns:
    bool, True if ancestor relationship exists
    """

def ancestor(nid, level=None) -> str | None:
    """
    Get ancestor at specific level or immediate ancestor.
    
    Parameters:
    - nid: str, node identifier
    - level: int, ancestor level (optional)
    
    Returns:
    str, ancestor node identifier or None
    """

Usage Examples:

# Check ancestry
if tree.is_ancestor("company", "alice"):
    print("Alice works for the company")

# Get specific level ancestor
dept_manager = tree.ancestor("alice", level=1)
if dept_manager:
    print(f"Alice's department: {tree[dept_manager].tag}")

# Get immediate parent (ancestor without level)
immediate_parent = tree.ancestor("alice")

Path Operations

Find and analyze paths between nodes.

def paths_to_leaves() -> list[list[str]]:
    """
    Get all paths from root to leaf nodes.
    
    Returns:
    list[list[str]], list of paths (each path is list of node identifiers)
    """

Usage Examples:

# Get all root-to-leaf paths
all_paths = tree.paths_to_leaves()
for path in all_paths:
    path_names = [tree[nid].tag for nid in path]
    print(f"Path: {' -> '.join(path_names)}")

# Find paths to specific conditions
leaf_paths = []
for path in tree.paths_to_leaves():
    leaf_node = tree[path[-1]]
    if leaf_node.data and leaf_node.data.get("role") == "engineer":
        leaf_paths.append(path)

Advanced Traversal Patterns

Complex traversal patterns and custom navigation logic.

Usage Examples:

# Custom traversal with state tracking
visited = set()
for node_id in tree.expand_tree():
    if node_id not in visited:
        node = tree[node_id]
        print(f"First visit: {node.tag}")
        visited.add(node_id)

# Level-order processing
current_level = 0
for node_id in tree.expand_tree(mode=Tree.WIDTH):
    node_level = tree.level(node_id)
    if node_level != current_level:
        print(f"\n--- Level {node_level} ---")
        current_level = node_level
    print(f"  {tree[node_id].tag}")

# Conditional subtree traversal
def should_explore_subtree(node):
    return node.data and node.data.get("active", True)

for node_id in tree.expand_tree(filter=lambda n: should_explore_subtree(n)):
    print(f"Active branch: {tree[node_id].tag}")

# Reverse depth-first (post-order style)
nodes = list(tree.expand_tree())
for node_id in reversed(nodes):
    print(f"Post-order: {tree[node_id].tag}")

Traversal Constants

ROOT = 0     # Tree traversal starting from root level
DEPTH = 1    # Depth-first traversal mode (pre-order)
WIDTH = 2    # Breadth-first traversal mode (level-order)  
ZIGZAG = 3   # Zigzag traversal mode (alternating left-right)

Performance Considerations

expand_tree(): O(n) for full traversal, memory-efficient iterator
children(): O(1) lookup, returns list copy
parent(): O(1) lookup via internal node references
level(): O(h) where h is tree height
is_ancestor(): O(h) traversal up ancestry chain
paths_to_leaves(): O(n*h) generates all paths

Optimization Tips:

# Use iterators for large trees
for node_id in tree.expand_tree():  # Memory efficient
    process_node(tree[node_id])

# Cache expensive operations
tree_depth = tree.depth()  # Cache if used multiple times
leaf_nodes = tree.leaves()  # Cache for repeated access

# Filter early for better performance
large_projects = tree.expand_tree(
    filter=lambda n: n.data and n.data.get("size", 0) > 1000
)

Install with Tessl CLI