tessl/pypi-treeswift

TreeSwift: Fast tree module for Python 2 and 3 - A Python library for parsing, manipulating, and iterating over rooted tree structures with emphasis on performance and speed.

Overview

Eval results

Files

Tree Traversal

Name: tessl/pypi-treeswift
Author: tessl

TreeSwift provides comprehensive tree traversal methods implemented as memory-efficient generators. All traversal methods support filtering by node type (leaves, internal nodes, or both) and provide flexible iteration patterns for different algorithmic needs.

Capabilities

Preorder Traversal

Visits nodes in preorder: current node first, then recursively visit children. Useful for top-down tree processing and copying operations.

def traverse_preorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """
    Perform preorder traversal starting at this node.

    Parameters:
    - leaves (bool): Include leaf nodes in traversal
    - internal (bool): Include internal nodes in traversal

    Yields:
    - Node: Nodes in preorder sequence
    """

Usage examples:

import treeswift

tree = treeswift.read_tree_newick("((A,B),(C,D));")

# Traverse all nodes in preorder
for node in tree.traverse_preorder():
    print(f"Node: {node.get_label()}, is_leaf: {node.is_leaf()}")

# Traverse only leaves
for leaf in tree.traverse_preorder(internal=False):
    print(f"Leaf: {leaf.get_label()}")

# Traverse only internal nodes
for internal_node in tree.traverse_preorder(leaves=False):
    print(f"Internal node with {internal_node.num_children()} children")

Postorder Traversal

Visits children first, then the current node. Essential for bottom-up computations like calculating subtree statistics.

def traverse_postorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """
    Perform postorder traversal starting at this node.

    Parameters:
    - leaves (bool): Include leaf nodes in traversal
    - internal (bool): Include internal nodes in traversal

    Yields:
    - Node: Nodes in postorder sequence
    """

Usage examples:

import treeswift

tree = treeswift.read_tree_newick("((A:0.1,B:0.2):0.5,(C:0.3,D:0.4):0.6):0.0;")

# Calculate subtree sums in postorder
subtree_sums = {}
for node in tree.traverse_postorder():
    if node.is_leaf():
        subtree_sums[node] = node.get_edge_length() or 0
    else:
        subtree_sums[node] = sum(subtree_sums[child] for child in node.children)
        if node.get_edge_length():
            subtree_sums[node] += node.get_edge_length()

print(f"Total tree length: {subtree_sums[tree.root]}")

Level-order Traversal

Visits nodes level by level (breadth-first), useful for level-based algorithms and visualization.

def traverse_levelorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """
    Perform level-order (breadth-first) traversal starting at this node.

    Parameters:
    - leaves (bool): Include leaf nodes in traversal
    - internal (bool): Include internal nodes in traversal

    Yields:
    - Node: Nodes in level-order sequence
    """

Usage examples:

import treeswift

tree = treeswift.read_tree_newick("(((A,B),C),((D,E),F));")

# Print tree structure level by level
current_level = 0
nodes_at_level = []

for node in tree.traverse_levelorder():
    # Calculate node depth
    depth = 0
    curr = node
    while curr.parent is not None:
        depth += 1
        curr = curr.parent
    
    if depth > current_level:
        if nodes_at_level:
            print(f"Level {current_level}: {[n.get_label() or 'internal' for n in nodes_at_level]}")
        current_level = depth
        nodes_at_level = []
    
    nodes_at_level.append(node)

if nodes_at_level:
    print(f"Level {current_level}: {[n.get_label() or 'internal' for n in nodes_at_level]}")

Inorder Traversal

For binary trees, visits left subtree, current node, then right subtree. Raises error for non-binary trees.

def traverse_inorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """
    Perform inorder traversal starting at this node (binary trees only).

    Parameters:
    - leaves (bool): Include leaf nodes in traversal
    - internal (bool): Include internal nodes in traversal

    Yields:
    - Node: Nodes in inorder sequence

    Raises:
    - RuntimeError: If tree contains non-binary nodes
    """

Usage examples:

import treeswift

# Binary tree
tree = treeswift.read_tree_newick("((A,B),(C,D));")

try:
    for node in tree.traverse_inorder():
        print(f"Node: {node.get_label() or 'internal'}")
except RuntimeError as e:
    print(f"Error: {e}")

# This will raise an error (non-binary)
try:
    tree = treeswift.read_tree_newick("(A,B,C);")
    for node in tree.traverse_inorder():
        print(node)
except RuntimeError as e:
    print(f"Cannot perform inorder on non-binary tree: {e}")

Root Distance Order Traversal

Visits nodes ordered by their distance from the root, either ascending or descending.

def traverse_rootdistorder(self, ascending: bool = True, leaves: bool = True, internal: bool = True) -> Generator[tuple[float, Node], None, None]:
    """
    Traverse nodes ordered by distance from root.

    Parameters:
    - ascending (bool): True for ascending distance order, False for descending
    - leaves (bool): Include leaf nodes in traversal
    - internal (bool): Include internal nodes in traversal

    Yields:
    - tuple[float, Node]: (distance_from_root, node) pairs in distance order
    """

Usage examples:

import treeswift

tree = treeswift.read_tree_newick("((A:0.1,B:0.2):0.3,(C:0.4,D:0.5):0.6):0.0;")

# Nodes by increasing distance from root
print("Nodes by distance from root (ascending):")
for distance, node in tree.traverse_rootdistorder(ascending=True):
    label = node.get_label() or "internal"
    print(f"  {distance:.1f}: {label}")

# Nodes by decreasing distance from root (leaves first)
print("\nNodes by distance from root (descending):")
for distance, node in tree.traverse_rootdistorder(ascending=False):
    label = node.get_label() or "internal"
    print(f"  {distance:.1f}: {label}")

# Only leaves by distance
print("\nLeaves by distance from root:")
for distance, node in tree.traverse_rootdistorder(internal=False):
    print(f"  {distance:.1f}: {node.get_label()}")

Specialized Traversal Methods

Convenience methods for specific node types.

def traverse_leaves(self) -> Generator[Node, None, None]:
    """Traverse only leaf nodes (convenience method)."""

def traverse_internal(self) -> Generator[Node, None, None]:
    """Traverse only internal nodes (convenience method)."""

Usage examples:

import treeswift

tree = treeswift.read_tree_newick("((A,B),(C,D));")

# Get all leaf labels
leaf_labels = [node.get_label() for node in tree.traverse_leaves()]
print(f"Leaves: {leaf_labels}")

# Count internal nodes
internal_count = sum(1 for node in tree.traverse_internal())
print(f"Internal nodes: {internal_count}")

Node-level Traversal Methods

Individual nodes also support traversal methods for subtree operations.

# Node class methods
def traverse_preorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """Preorder traversal starting from this node."""

def traverse_postorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """Postorder traversal starting from this node."""

def traverse_levelorder(self, leaves: bool = True, internal: bool = True) -> Generator[Node, None, None]:
    """Level-order traversal starting from this node."""

def traverse_ancestors(self, include_self: bool = True) -> Generator[Node, None, None]:
    """Traverse ancestors of this node toward root."""

def traverse_bfs(self, include_self: bool = True) -> Generator[tuple[Node, float], None, None]:
    """Breadth-first search yielding (node, distance) pairs."""

Usage examples:

import treeswift

tree = treeswift.read_tree_newick("(((A,B),C),((D,E),F));")

# Find a specific leaf and traverse its ancestors
for node in tree.traverse_leaves():
    if node.get_label() == "A":
        print("Ancestors of A:")
        for ancestor in node.traverse_ancestors():
            label = ancestor.get_label() or f"internal({ancestor.num_children()} children)"
            print(f"  {label}")
        break

# BFS from a specific internal node
internal_nodes = list(tree.traverse_internal())
if internal_nodes:
    start_node = internal_nodes[0]
    print(f"\nBFS from internal node:")
    for node, distance in start_node.traverse_bfs():
        label = node.get_label() or "internal"
        print(f"  Distance {distance}: {label}")

Install with Tessl CLI