#!/usr/bin/env python
# Copyright (C) 2011
# Brett Alistair Kromkamp - brettkromkamp@gmail.com
# Copyright (C) 2012-2025
# Xiaming Chen - chenxm35@gmail.com
# and other contributors.
# All rights reserved.
"""
Node structure in treelib.
A :class:`Node` object contains basic properties such as node identifier,
node tag, parent node, children nodes etc., and some operations for a node.
The Node class is the fundamental building block of a Tree. Each node can store:
- A unique identifier for tree operations
- A human-readable tag for display
- Custom data payload
- Parent-child relationships within one or more trees
Note:
Nodes are typically created through Tree.create_node() rather than
directly instantiated, as the Tree class manages the parent-child
relationships automatically.
"""
from __future__ import unicode_literals
import copy
import sys
import uuid
from collections import defaultdict
from typing import Any, List, Optional, Union, cast
from warnings import warn
from .exceptions import NodePropertyError
from .misc import deprecated
if sys.version_info >= (3, 9):
StrList = list[str]
else:
StrList = List[str] # Python 3.8 and earlier
[docs]
class Node(object):
"""
Elementary node object stored in Tree structures.
A Node represents a single element in a tree hierarchy. Each node maintains
references to its parent and children within specific tree contexts, along
with a human-readable tag and optional data payload.
Attributes:
identifier (str): Unique identifier for this node within a tree.
tag (str): Human-readable label for display purposes.
expanded (bool): Controls visibility of children in tree displays.
data (Any): User-defined payload associated with this node.
Example:
Creating nodes with different configurations::
# Basic node
node = Node("Root", "root")
# Node with custom data
node = Node("File", "file1", data={"size": 1024, "type": "txt"})
# Node that starts collapsed
node = Node("Folder", "folder1", expanded=False)
Warning:
While nodes can be created directly, it's recommended to use
Tree.create_node() which properly manages tree relationships.
"""
#: Mode constants for routine `update_fpointer()`.
(ADD, DELETE, INSERT, REPLACE) = list(range(4))
def __init__(
self,
tag: Optional[str] = None,
identifier: Optional[str] = None,
expanded: bool = True,
data: Any = None,
) -> None:
"""
Create a new Node object to be placed inside a Tree object.
Args:
tag: Human-readable label for the node. If None, uses identifier.
identifier: Unique ID for the node. If None, generates a UUID.
expanded: Whether node children are visible in tree displays.
data: Optional user data to associate with this node.
Example:
Creating different types of nodes::
# Auto-generated identifier
node1 = Node("My Node")
# Explicit identifier
node2 = Node("Root", "root")
# With custom data
node3 = Node("User", "user1", data={"name": "Alice", "role": "admin"})
# Initially collapsed
node4 = Node("Large Folder", "folder", expanded=False)
"""
#: if given as a parameter, must be unique
self._identifier: Optional[str] = None
self._set_identifier(identifier)
#: None or something else
#: if None, self._identifier will be set to the identifier's value.
if tag is None:
self._tag = self._identifier
else:
self._tag = tag
#: boolean
self.expanded = expanded
#: identifier of the parent's node :
self._predecessor: dict = {}
#: identifier(s) of the soons' node(s) :
self._successors: dict = defaultdict(list)
#: User payload associated with this node.
self.data = data
# for retro-compatibility on bpointer/fpointer
self._initial_tree_id: Optional[str] = None
def __lt__(self, other) -> bool:
"""
Compare nodes for sorting based on their tags.
Enables sorting of Node objects in collections by comparing their tag attributes.
This allows natural ordering when displaying or processing collections of nodes.
Args:
other: Another Node object to compare with.
Returns:
bool: True if this node's tag is lexicographically less than other's tag.
Example:
Sorting nodes by tag::
nodes = [Node("Charlie", "c"), Node("Alice", "a"), Node("Bob", "b")]
sorted_nodes = sorted(nodes) # Alice, Bob, Charlie
"""
return self.tag < other.tag
[docs]
def set_initial_tree_id(self, tree_id: str) -> None:
"""
Set the initial tree identifier for backward compatibility.
This method is used internally to maintain compatibility with older
node pointer systems. Each node remembers the first tree it was added to
for legacy bpointer/fpointer access.
Args:
tree_id: Unique identifier of the tree this node was first added to.
Note:
This is an internal method used for legacy compatibility.
Modern code should use the tree-specific pointer methods instead.
"""
if self._initial_tree_id is None:
self._initial_tree_id = tree_id
def _set_identifier(self, nid: Optional[str]) -> None:
"""
Initialize node identifier with given value or auto-generate one.
Private method used during node creation to set the unique identifier.
If no identifier is provided, generates a UUID automatically to ensure
uniqueness within the tree.
Args:
nid: Desired node identifier, or None to auto-generate.
Note:
This is an internal method. Use the identifier property for
accessing or modifying the identifier after node creation.
"""
if nid is None:
self._identifier = str(uuid.uuid1())
else:
self._identifier = nid
@property
@deprecated(alias="node.predecessor")
def bpointer(self):
if self._initial_tree_id not in self._predecessor.keys():
return None
return self._predecessor[self._initial_tree_id]
@bpointer.setter
@deprecated(alias="node.set_predecessor")
def bpointer(self, value) -> None:
self.set_predecessor(value, self._initial_tree_id)
[docs]
@deprecated(alias="node.set_predecessor")
def update_bpointer(self, nid) -> None:
self.set_predecessor(nid, self._initial_tree_id)
@property
@deprecated(alias="node.successors")
def fpointer(self):
if self._initial_tree_id not in self._successors:
return []
return self._successors[self._initial_tree_id]
@fpointer.setter
@deprecated(alias="node.update_successors")
def fpointer(self, value: Union[None, list, dict, set]) -> None:
self.set_successors(value, tree_id=self._initial_tree_id)
[docs]
@deprecated(alias="node.update_successors")
def update_fpointer(self, nid, mode=ADD, replace=None):
self.update_successors(nid, mode, replace, self._initial_tree_id)
[docs]
def predecessor(self, tree_id):
"""
Get the parent node identifier in the specified tree.
Since nodes can exist in multiple trees simultaneously, this method
returns the parent identifier for this node within a specific tree context.
Args:
tree_id: Identifier of the tree to query parent relationship in.
Returns:
str or None: Parent node identifier, or None if this is a root node.
Example:
Accessing parent in different trees::
# Node can have different parents in different trees
parent_id = node.predecessor("tree1")
if parent_id:
print(f"Parent in tree1: {parent_id}")
"""
return self._predecessor[tree_id]
[docs]
def set_predecessor(self, nid: Optional[str], tree_id: Optional[str]) -> None:
"""
Set the parent node identifier for this node in a specific tree.
Establishes or updates the parent-child relationship for this node
within the context of a particular tree. Used internally by tree
operations to maintain proper hierarchy.
Args:
nid: Parent node identifier, or None to make this a root node.
tree_id: Identifier of the tree to set parent relationship in.
Example:
Setting parent relationship::
node.set_predecessor("parent_id", "tree1")
node.set_predecessor(None, "tree1") # Make root
"""
self._predecessor[tree_id] = nid
[docs]
def successors(self, tree_id: Optional[str]) -> StrList:
"""
Get the list of child node identifiers in the specified tree.
Returns all direct children of this node within a specific tree context.
Children are maintained as an ordered list to preserve insertion order
and support custom sorting.
Args:
tree_id: Identifier of the tree to query children in.
Returns:
list[str]: List of child node identifiers. Empty list if no children.
Example:
Accessing children in different trees::
children = node.successors("tree1")
for child_id in children:
print(f"Child: {child_id}")
# Node can have different children in different trees
tree1_children = node.successors("tree1")
tree2_children = node.successors("tree2")
"""
return self._successors[tree_id]
[docs]
def set_successors(self, value: Union[None, list, dict, set], tree_id: Optional[str] = None) -> None:
"""
Set the complete list of child node identifiers for a specific tree.
Replaces the entire children list with new values. Accepts multiple
input formats for flexibility: list, set, dict (uses keys), or None.
Args:
value: New children collection. Can be:
- list: Used directly as child identifiers
- set: Converted to list of identifiers
- dict: Uses dictionary keys as identifiers
- None: Sets empty children list
tree_id: Identifier of the tree to set children in.
Raises:
NotImplementedError: If value type is not supported.
Example:
Setting children from different sources::
# From list
node.set_successors(["child1", "child2"], "tree1")
# From set
node.set_successors({"child1", "child2"}, "tree1")
# From dict (uses keys)
node.set_successors({"child1": data1, "child2": data2}, "tree1")
# Clear children
node.set_successors(None, "tree1")
"""
setter_lookup = {
"NoneType": lambda x: list(),
"list": lambda x: x,
"dict": lambda x: list(x.keys()),
"set": lambda x: list(x),
}
t = value.__class__.__name__
if t in setter_lookup:
f_setter = setter_lookup[t]
self._successors[tree_id] = f_setter(value)
else:
raise NotImplementedError("Unsupported value type %s" % t)
[docs]
def update_successors(
self,
nid: Optional[str],
mode: int = ADD,
replace: Optional[str] = None,
tree_id: Optional[str] = None,
) -> None:
"""
Update the children list with different modification modes.
Provides granular control over child node list modifications without
replacing the entire list. Supports adding, removing, and replacing
individual child references.
Args:
nid: Child node identifier to operate on.
mode: Operation type using Node constants:
- Node.ADD: Append child to end of list
- Node.DELETE: Remove child from list
- Node.INSERT: Deprecated, same as ADD
- Node.REPLACE: Replace child with another identifier
replace: New identifier when mode=REPLACE. Required for replace mode.
tree_id: Identifier of the tree to modify children in.
Raises:
NodePropertyError: If replace is None when mode=REPLACE.
NotImplementedError: If mode is not supported.
Example:
Different update operations::
# Add a child
node.update_successors("new_child", Node.ADD, tree_id="tree1")
# Remove a child
node.update_successors("old_child", Node.DELETE, tree_id="tree1")
# Replace a child
node.update_successors("old_child", Node.REPLACE,
replace="new_child", tree_id="tree1")
"""
if nid is None:
return
def _manipulator_append() -> None:
self.successors(tree_id).append(nid)
def _manipulator_delete() -> None:
if nid in self.successors(tree_id):
self.successors(tree_id).remove(nid)
else:
warn("Nid %s wasn't present in fpointer" % nid)
def _manipulator_insert() -> None:
warn("WARNING: INSERT is deprecated to ADD mode")
self.update_successors(nid, tree_id=tree_id)
def _manipulator_replace() -> None:
if replace is None:
raise NodePropertyError('Argument "replace" should be provided when mode is {}'.format(mode))
ind = self.successors(tree_id).index(nid)
self.successors(tree_id)[ind] = replace
manipulator_lookup = {
self.ADD: "_manipulator_append",
self.DELETE: "_manipulator_delete",
self.INSERT: "_manipulator_insert",
self.REPLACE: "_manipulator_replace",
}
if mode not in manipulator_lookup:
raise NotImplementedError("Unsupported node updating mode %s" % str(mode))
f_name = cast(str, manipulator_lookup.get(mode))
f = locals()[f_name]
return f()
@property
def identifier(self) -> str:
"""
Get the unique identifier of this node.
The identifier serves as the primary key for this node within tree structures.
It must be unique within each tree that contains this node. Used for all
tree operations including lookup, traversal, and relationship management.
Returns:
str: The unique node identifier.
Example:
Accessing node identifier::
node = Node("My Node", "unique_id")
print(node.identifier) # "unique_id"
# Use in tree operations
tree[node.identifier] # Access via identifier
"""
return cast(str, self._identifier)
[docs]
def clone_pointers(self, former_tree_id: str, new_tree_id: str) -> None:
"""
Clone parent-child relationships from one tree context to another.
Copies the complete relationship structure (parent and children) from
one tree context to a new tree context. Used when moving or copying
nodes between trees while preserving their hierarchical relationships.
Args:
former_tree_id: Source tree identifier to copy relationships from.
new_tree_id: Target tree identifier to copy relationships to.
Example:
Cloning relationships between trees::
# Copy node relationships from tree1 to tree2
node.clone_pointers("tree1", "tree2")
# Now node has same relationships in both trees
assert node.predecessor("tree1") == node.predecessor("tree2")
"""
former_bpointer = self.predecessor(former_tree_id)
self.set_predecessor(former_bpointer, new_tree_id)
former_fpointer = self.successors(former_tree_id)
# fpointer is a list and would be copied by reference without deepcopy
self.set_successors(copy.deepcopy(former_fpointer), tree_id=new_tree_id)
[docs]
def reset_pointers(self, tree_id) -> None:
"""
Reset all parent-child relationships for a specific tree context.
Clears both parent and children references for this node within the
specified tree, effectively making it an isolated node. Used during
tree restructuring operations.
Args:
tree_id: Identifier of the tree to reset relationships in.
Example:
Resetting node relationships::
# Clear all relationships in tree1
node.reset_pointers("tree1")
# Node now has no parent or children in tree1
assert node.predecessor("tree1") is None
assert len(node.successors("tree1")) == 0
"""
self.set_predecessor(None, tree_id)
self.set_successors([], tree_id=tree_id)
@identifier.setter # type: ignore
def identifier(self, value: str) -> None:
"""
Set the unique identifier of this node.
Updates the node's identifier while maintaining data integrity.
The new identifier must be unique within any trees containing this node.
Args:
value: New unique identifier for this node. Cannot be None.
Warning:
Changing a node's identifier while it exists in trees can break
tree integrity. Use Tree.update_node() for safe identifier changes.
Example:
Updating node identifier::
node.identifier = "new_unique_id"
# Better approach when node is in a tree:
tree.update_node("old_id", identifier="new_id")
"""
if value is None:
print("WARNING: node ID can not be None")
else:
self._set_identifier(value)
[docs]
def is_leaf(self, tree_id: Optional[str] = None) -> bool:
"""
Check if this node is a leaf (has no children) in the specified tree.
A leaf node is one that has no child nodes. This is a fundamental
property used in tree algorithms and can vary between different
tree contexts if the node exists in multiple trees.
Args:
tree_id: Identifier of the tree to check leaf status in.
If None, uses the initial tree for backward compatibility.
Returns:
bool: True if node has no children in the specified tree, False otherwise.
Example:
Checking leaf status::
if node.is_leaf("tree1"):
print("This is a leaf node")
# Different trees may have different leaf status
is_leaf_tree1 = node.is_leaf("tree1")
is_leaf_tree2 = node.is_leaf("tree2") # May differ
"""
if tree_id is None:
# for retro-compatilibity
if self._initial_tree_id not in self._successors.keys():
return True
else:
tree_id = self._initial_tree_id
if len(self.successors(tree_id)) == 0:
return True
else:
return False
[docs]
def is_root(self, tree_id: Optional[str] = None) -> bool:
"""
Check if this node is a root (has no parent) in the specified tree.
A root node is the topmost node in a tree hierarchy with no parent.
Every tree has exactly one root node. This status can vary between
different tree contexts if the node exists in multiple trees.
Args:
tree_id: Identifier of the tree to check root status in.
If None, uses the initial tree for backward compatibility.
Returns:
bool: True if node has no parent in the specified tree, False otherwise.
Example:
Checking root status::
if node.is_root("tree1"):
print("This is the root node")
# Same node might be root in one tree but not another
is_root_tree1 = node.is_root("tree1")
is_root_tree2 = node.is_root("tree2") # May differ
"""
if tree_id is None:
# for retro-compatilibity
if self._initial_tree_id not in self._predecessor.keys():
return True
else:
tree_id = self._initial_tree_id
return self.predecessor(tree_id) is None
@property
def tag(self) -> str:
"""
Get the human-readable display name of this node.
The tag serves as the display label for this node in tree visualizations,
printouts, and user interfaces. Unlike the identifier, the tag doesn't
need to be unique and is primarily for human readability.
Returns:
str: The display name/label for this node.
Example:
Using node tags for display::
node = Node("User Profile", "user123")
print(node.tag) # "User Profile"
print(node.identifier) # "user123"
# Tags are used in tree display
tree.show() # Shows "User Profile" not "user123"
"""
return cast(str, self._tag)
@tag.setter
def tag(self, value: Optional[str]) -> None:
"""
Set the human-readable display name of this node.
Updates the display label used in tree visualizations and string
representations. The tag can be changed freely without affecting
tree structure or node relationships.
Args:
value: New display name for the node. Can be None.
Example:
Updating node display name::
node.tag = "Updated Profile"
print(node.tag) # "Updated Profile"
# Useful for dynamic labeling
node.tag = f"User: {user.name} (Active)"
"""
self._tag = value if value is not None else None
def __repr__(self) -> str:
"""
Return detailed string representation of this node for debugging.
Provides a comprehensive view of the node's properties including
tag, identifier, and data. Useful for debugging, logging, and
development work.
Returns:
str: Detailed string representation in format:
Node(tag=<tag>, identifier=<id>, data=<data>)
Example:
Node representation output::
node = Node("Profile", "user123", data={"age": 30})
print(repr(node))
# Output: Node(tag=Profile, identifier=user123, data={'age': 30})
# Useful in lists and debugging
print([node1, node2]) # Shows detailed info for each node
"""
name = self.__class__.__name__
kwargs = [
"tag={0}".format(self.tag),
"identifier={0}".format(self.identifier),
"data={0}".format(self.data),
]
return "%s(%s)" % (name, ", ".join(kwargs))