Skip to content

tree

TreeNode 

TreeNode(value: Any)

Bases: Generic[_TreeNodeT]

A tree node with parent/child links and path traversal helpers.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> child.parent is root
True

Initialize a TreeNode instance.

Parameters:

  • value (Any) –

    The value to be stored in the node.

Examples:

>>> node = TreeNode("root")
>>> node.value
'root'
Source code in ures/data_structure/tree.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def __init__(self, value: Any):
    """
    Initialize a TreeNode instance.

    Args:
        value (Any): The value to be stored in the node.

    Examples:
        >>> node = TreeNode("root")
        >>> node.value
        'root'
    """
    self._parent: _TreeNodeT | None = None
    self._children: dict[str, _TreeNodeT] = {}
    self._value: Any = value
    self._id = uuid.uuid4().hex

parent property 

parent: _TreeNodeT | None

Get the parent node of this TreeNode.

Returns:

  • _TreeNodeT | None –

    Optional[_TreeNodeT]: The parent node if it exists; otherwise, None.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> child.set_parent(root)
>>> child.parent is root
True

children property 

children: dict[str, _TreeNodeT]

Get the dictionary of child nodes.

Returns:

  • dict[str, _TreeNodeT] –

    dict[str, _TreeNodeT]: A dictionary mapping each child's unique ID to its TreeNode instance.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> list(root.children.values())[0].value
'child'

is_leaf property 

is_leaf: bool

Determine if the node is a leaf (i.e., has no children).

Returns:

  • bool ( bool ) –

    True if the node has no children; otherwise, False.

Examples:

>>> node = TreeNode("leaf")
>>> node.is_leaf
True

value property 

value: Any

Retrieve the value stored in the node.

Returns:

  • Any ( Any ) –

    The value of the node.

Examples:

>>> node = TreeNode(10)
>>> node.value
10

id property 

id: str

Get the unique identifier of the node.

Returns:

  • str ( str ) –

    A unique hexadecimal string identifier for the node.

Examples:

>>> node = TreeNode("example")
>>> isinstance(node.id, str)
True

add_child 

add_child(child: _TreeNodeT)

Add a child node to the current node.

This method adds the given child to the node's children dictionary (using the child's ID as key) and sets the current node as the parent of the child.

Parameters:

  • child (TreeNode) –

    The child node to add.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> child.parent is root
True
Source code in ures/data_structure/tree.py 
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
def add_child(self, child: _TreeNodeT):
    """
    Add a child node to the current node.

    This method adds the given child to the node's children dictionary (using the child's ID as key)
    and sets the current node as the parent of the child.

    Args:
        child (TreeNode): The child node to add.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> root.add_child(child)
        >>> child.parent is root
        True
    """
    if child.id not in self.children:
        self._children[child.id] = child
        child.set_parent(self)

remove_child 

remove_child(child: TreeNode)

Remove a child node from the current node.

This method removes the specified child node from the current node's children and clears the child's parent reference.

Parameters:

  • child (TreeNode) –

    The child node to remove.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> root.add_child(child)
>>> root.remove_child(child)
>>> child.parent is None
True
Source code in ures/data_structure/tree.py 
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
def remove_child(self, child: TreeNode):
    """
    Remove a child node from the current node.

    This method removes the specified child node from the current node's children and clears the
    child's parent reference.

    Args:
        child (TreeNode): The child node to remove.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> root.add_child(child)
        >>> root.remove_child(child)
        >>> child.parent is None
        True
    """
    if child.id in self.children:
        self._children.pop(child.id)
        child.set_parent(None)

set_parent 

set_parent(parent: _TreeNodeT | None)

Set the parent of the current node.

If the node already has a parent, it will be removed from that parent's children before setting the new parent.

Parameters:

  • parent (TreeNode | None) –

    The new parent node. If None, the node will have no parent.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> child.set_parent(root)
>>> child.parent is root
True
Source code in ures/data_structure/tree.py 
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
def set_parent(self, parent: _TreeNodeT | None):
    """
    Set the parent of the current node.

    If the node already has a parent, it will be removed from that parent's children before setting
    the new parent.

    Args:
        parent (TreeNode | None): The new parent node. If None, the node will have no parent.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> child.set_parent(root)
        >>> child.parent is root
        True
    """
    if parent is not None:
        if isinstance(self.parent, TreeNode):
            self.parent.remove_child(self)
    self._parent = parent

backward_stack 

backward_stack() -> Iterator[TreeNode]

Generate an iterator for the path from the current node to the root.

The iterator yields nodes starting with the current node and then each successive parent until no further parent exists.

Returns:

  • Iterator[TreeNode] –

    Iterator[TreeNode]: An iterator over the nodes from the current node up to the root.

Examples:

>>> root = TreeNode("root")
>>> child = TreeNode("child")
>>> child.set_parent(root)
>>> "/".join(node.value for node in child.backward_stack())
'child/root'
Source code in ures/data_structure/tree.py 
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
def backward_stack(self) -> Iterator[TreeNode]:
    """
    Generate an iterator for the path from the current node to the root.

    The iterator yields nodes starting with the current node and then each successive parent until
    no further parent exists.

    Returns:
        Iterator[TreeNode]: An iterator over the nodes from the current node up to the root.

    Examples:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> child.set_parent(root)
        >>> "/".join(node.value for node in child.backward_stack())
        'child/root'
    """
    current = self
    while current is not None:
        yield current
        current = current.parent

forward_stack 

forward_stack(**kwargs) -> list[list[Any]]

Get all forward paths from the current node to each leaf node.

This method performs a depth-first search (DFS) to compute every possible path from the current node to all leaf nodes. If an optional attribute key is provided via kwargs, the method returns that attribute for each node in the path; otherwise, it returns the node itself.

Other Parameters:

  • attr (str) –

    The attribute name to extract from each node. Defaults to None.

Returns:

  • list[list[Any]] –

    list[list[Any]]: A list of paths, where each path is a list of nodes or attribute values from the current node to a leaf node.

Examples:

>>> root = TreeNode("root")
>>> child1 = TreeNode("child1")
>>> child2 = TreeNode("child2")
>>> root.add_child(child1)
>>> root.add_child(child2)
>>> paths = root.forward_stack(attr="value")
>>> sorted(paths)
[['child1', 'root'], ['child2', 'root']]  # Order may vary
Source code in ures/data_structure/tree.py 
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
def forward_stack(self, **kwargs) -> list[list[Any]]:
    """
    Get all forward paths from the current node to each leaf node.

    This method performs a depth-first search (DFS) to compute every possible path from the current node
    to all leaf nodes. If an optional attribute key is provided via kwargs, the method returns that attribute
    for each node in the path; otherwise, it returns the node itself.

    Keyword Args:
        attr (str, optional): The attribute name to extract from each node. Defaults to None.

    Returns:
        list[list[Any]]: A list of paths, where each path is a list of nodes or attribute values from the
                         current node to a leaf node.

    Examples:
        >>> root = TreeNode("root")
        >>> child1 = TreeNode("child1")
        >>> child2 = TreeNode("child2")
        >>> root.add_child(child1)
        >>> root.add_child(child2)
        >>> paths = root.forward_stack(attr="value")
        >>> sorted(paths)
        [['child1', 'root'], ['child2', 'root']]  # Order may vary
    """
    all_paths = []
    self._dfs(cast(_TreeNodeT, self), [], all_paths, **kwargs)
    return all_paths