How to Move a Node to a Different Parent in treelib

Use Tree.move_node(source, destination) to relocate any node or subtree to a new parent while preserving structural integrity.

The caesar0301/treelib library provides a lightweight Python implementation for tree data structures. When you need to reorganize your hierarchy, moving a node to a different parent is a common operation handled by the Tree class. This article explains how to move a node to a different parent in treelib using the actual source code implementation as reference.

Understanding Tree.move_node()

According to the caesar0301/treelib source code, the Tree.move_node() method defined in treelib/tree.py around line 1324 is the primary API for relocating nodes. The method performs atomic updates to the tree's internal pointers while enforcing structural constraints.

Method Signature and Parameters

The method signature is straightforward:

Tree.move_node(source: str, destination: str) -> None

• source – The identifier of the node (and its entire subtree) you want to relocate.
• destination – The identifier of the node that will become the new parent.

Both parameters are strings representing unique node identifiers. The method returns None and modifies the tree structure in-place.

Internal Mechanics

The implementation performs three discrete operations to maintain tree integrity:

1. Validation – Checks that both identifiers exist in the tree. Raises NodeIDAbsentError (defined in treelib/exceptions.py) if either node is missing. Validates that the move would not create a circular reference, raising LoopError if the destination is a descendant of the source.

2. Detach – Removes the source node from its current parent by updating the forward pointer of the old parent using the private __update_fpointer helper method.

3. Attach – Links the source node to the new parent and updates the backward pointer of the source node using __update_bpointer.

These low-level pointer updates manipulate the underlying node relationships stored in treelib/node.py, ensuring the tree remains consistent throughout the operation.

Practical Code Examples

The following examples demonstrate how to move a node to a different parent in treelib, covering leaf nodes, entire subtrees, and error handling.

Moving a Leaf Node

Start by creating an organizational hierarchy, then move a single employee to a different department:

from treelib import Tree

# Build organization chart

tree = Tree()
tree.create_node("Company", "company")                     # root

tree.create_node("Engineering", "eng", parent="company")
tree.create_node("Sales", "sales", parent="company")

tree.create_node("Alice", "alice", parent="eng")
tree.create_node("Bob",   "bob",   parent="eng")
tree.create_node("Carol", "carol", parent="sales")

tree.show()

# └─ company

#    ├─ eng

#    │  ├─ alice

#    │  └─ bob

#    └─ sales

#       └─ carol

# Move Alice from Engineering to Sales

tree.move_node("alice", "sales")
tree.show()

# └─ company

#    ├─ eng

#    │  └─ bob

#    └─ sales

#       ├─ carol

#       └─ alice

Moving an Entire Subtree

When you move a non-leaf node, its entire subtree moves with it:

# Move the entire Engineering department under Sales

tree.move_node("eng", "sales")
tree.show()

# └─ company

#    └─ sales

#       ├─ carol

#       ├─ alice

#       └─ eng

#          └─ bob

Handling Circular References

The library prevents invalid operations that would break the tree structure. Attempting to move a node under one of its own descendants raises a LoopError defined in treelib/exceptions.py:

try:
    # Attempt to create a loop: move 'sales' under its own descendant 'bob'

    tree.move_node("sales", "bob")
except Exception as exc:
    print(type(exc).__name__, exc)   # LoopError ...

Error Handling and Validation

The move_node method relies on two primary exception types to enforce tree integrity:

• NodeIDAbsentError – Raised when either the source or destination identifier does not exist in the tree. This check occurs before any structural modifications.
• LoopError – Raised when the destination is a descendant of the source, which would create a circular reference. The validation logic traverses the ancestry chain to detect potential loops.

Both exceptions are declared in treelib/exceptions.py, and the validation phase ensures the tree remains in a consistent state even if the operation fails.

Summary

• Tree.move_node(source, destination) is the standard method to move a node to a different parent in treelib, implemented in treelib/tree.py at line 1324.
• The operation moves the entire subtree rooted at the source node, not just the node itself.
• The method performs three internal steps: validation, detachment from the old parent (via __update_fpointer), and attachment to the new parent (via __update_bpointer).
• Circular references are prevented by raising LoopError when the destination is a descendant of the source.
• Missing nodes trigger NodeIDAbsentError before any pointer modifications occur.

Frequently Asked Questions

Can I move the root node to a different parent?

No. The root node has no parent pointer to detach from, and the internal __update_fpointer logic expects a valid predecessor. Attempting to move the root node will raise an exception because the source node's current parent reference is invalid or None.

What happens to the children when I move a node?

All children move with the parent node. The move_node operation treats the source identifier as the root of a subtree; the entire branch is relocated to the new destination while maintaining internal relationships among the moved nodes. The backward pointers of all descendants remain unchanged during the move.

How do I check if a move would create a cycle before attempting it?

You can verify ancestry using Tree.is_ancestor(destination, source) before calling move_node. If this returns True, the destination is currently a descendant of the source, and moving the source under the destination would trigger a LoopError. This check mirrors the internal validation logic found in the source code.

Is there a way to move a node without knowing its current parent?

Yes. The move_node method only requires the source node's identifier, not its current parent. The implementation automatically handles the detachment phase by looking up the source node's current backward pointer (predecessor) via the Node class in treelib/node.py and updating the old parent's forward pointer list accordingly.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}