Skip to content

Data Structure - Tree

TreeNode

Bases: Generic[_TreeNodeT]

Source code in ures/data_structure/tree.py 
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
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
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
class TreeNode(Generic[_TreeNodeT]):
    def __init__(self, value: Any):
        """
        Initialize a TreeNode instance.

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

        Returns:
            None

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

    @property
    def parent(self) -> _TreeNodeT | None:
        """
        Get the parent node of this TreeNode.

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

        Example:
            >>> root = TreeNode("root")
            >>> child = TreeNode("child")
            >>> child.set_parent(root)
            >>> child.parent is root
            True
        """
        return self._parent

    @property
    def children(self) -> dict[str, _TreeNodeT]:
        """
        Get the dictionary of child nodes.

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

        Example:
            >>> root = TreeNode("root")
            >>> child = TreeNode("child")
            >>> root.add_child(child)
            >>> list(root.children.values())[0].value
            'child'
        """
        return self._children

    @property
    def is_leaf(self) -> bool:
        """
        Determine if the node is a leaf (i.e., has no children).

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

        Example:
            >>> node = TreeNode("leaf")
            >>> node.is_leaf
            True
        """
        return len(self.children) == 0

    @property
    def value(self) -> Any:
        """
        Retrieve the value stored in the node.

        Returns:
            Any: The value of the node.

        Example:
            >>> node = TreeNode(10)
            >>> node.value
            10
        """
        return self._value

    @property
    def id(self) -> str:
        """
        Get the unique identifier of the node.

        Returns:
            str: A unique hexadecimal string identifier for the node.

        Example:
            >>> node = TreeNode("example")
            >>> isinstance(node.id, str)
            True
        """
        return self._id

    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.

        Returns:
            None

        Example:
            >>> 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)

    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.

        Returns:
            None

        Example:
            >>> 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)

    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.

        Returns:
            None

        Example:
            >>> 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

    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.

        Example:
            >>> root = TreeNode("root")
            >>> child = TreeNode("child")
            >>> child.set_parent(root)
            >>> [node.value for node in child.backward_stack()]
            ['child', 'root']
        """
        current = self
        while current is not None:
            yield current
            current = current.parent

    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.

        Example:
            >>> 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

    def _dfs(self, node: _TreeNodeT, current_path: list, all_paths: list, **kwargs):
        """
        Recursively perform depth-first search (DFS) to find all paths from the given node to leaf nodes.

        This internal helper method accumulates paths by traversing each branch of the tree.
        If a keyword argument 'attr' is provided, it appends the value of that attribute for each node.

        Args:
            node (TreeNode): The current node in the DFS traversal.
            current_path (list): The path taken to reach the current node.
            all_paths (list): A list to store all complete paths.
            **kwargs: Optional keyword arguments.
                - attr (str, optional): The attribute name to use for each node in the path.

        Returns:
            None

        Example:
            >>> # Typically used internally by forward_stack.
            ... pass
        """
        assert isinstance(node, TreeNode)
        _attr = kwargs.get("attr", None)
        _key = node if _attr is None else getattr(node, _attr)
        current_path.append(_key)

        if not node.children:
            all_paths.append(list(current_path))
        else:
            for child in node.children.values():
                self._dfs(child, current_path, all_paths, **kwargs)
        current_path.pop()

children property

Get the dictionary of child nodes.

Returns:

Type Description
dict[str, _TreeNodeT]

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

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

id property

Get the unique identifier of the node.

Returns:

Name Type Description
str str

A unique hexadecimal string identifier for the node.
Example

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

is_leaf property

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

Returns:

Name Type Description
bool bool

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

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

parent property

Get the parent node of this TreeNode.

Returns:

Type Description
_TreeNodeT | None

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

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

value property

Retrieve the value stored in the node.

Returns:

Name Type Description
Any Any

The value of the node.
Example

node = TreeNode(10) node.value 10

__init__(value)

Initialize a TreeNode instance.

Parameters:

Name Type Description Default
value Any

The value to be stored in the node.

 required

Returns:

Type Description

None
Example

node = _TreeNodeT("root") node.value 'root'

Source code in ures/data_structure/tree.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def __init__(self, value: Any):
    """
    Initialize a TreeNode instance.

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

    Returns:
        None

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

add_child(child)

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:

Name Type Description Default
child TreeNode

The child node to add.

 required

Returns:

Type Description

None
Example

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

Source code in ures/data_structure/tree.py 
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
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.

    Returns:
        None

    Example:
        >>> 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)

backward_stack()

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:

Type Description
Iterator[TreeNode]

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

root = TreeNode("root") child = TreeNode("child") child.set_parent(root) [node.value for node in child.backward_stack()]['child', 'root']

Source code in ures/data_structure/tree.py 
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
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.

    Example:
        >>> root = TreeNode("root")
        >>> child = TreeNode("child")
        >>> child.set_parent(root)
        >>> [node.value for node in child.backward_stack()]
        ['child', 'root']
    """
    current = self
    while current is not None:
        yield current
        current = current.parent

forward_stack(**kwargs)

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:

Name Type Description
attr str

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

Returns:

Type Description
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.
Example

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 
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
231
232
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.

    Example:
        >>> 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

remove_child(child)

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:

Name Type Description Default
child TreeNode

The child node to remove.

 required

Returns:

Type Description

None
Example

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 
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
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.

    Returns:
        None

    Example:
        >>> 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(parent)

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:

Name Type Description Default
parent TreeNode | None

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

 required

Returns:

Type Description

None
Example

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

Source code in ures/data_structure/tree.py 
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
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.

    Returns:
        None

    Example:
        >>> 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