mergeRoots

MergeRoots is a procedure used in hierarchical data processing to combine two rooted trees into a single tree. The basic form creates a new root node and makes the original roots its children, thereby unifying the structures under one top-level node. This operation is common in tasks such as merging parse trees, fusing hierarchical metadata, and unifying tree-structured representations in knowledge graphs.

Variants of mergeRoots exist. In the simplest version, a new root is introduced and linked to the two existing roots without altering the internal structure of either tree. In an alternative variant, if the two roots share an identical label or identifier, the operation may merge them into a single root node, attaching all descendants from both trees beneath that shared root. Some implementations also offer non-destructive variants that preserve the original trees and return a new composite tree, as well as destructive variants that modify one of the input trees to become part of the merged structure.

Algorithm overview. Given rooted trees T1=(V1,E1,r1) and T2=(V2,E2,r2), the default non-destructive merge proceeds by creating a new root r and constructing a new tree T with V=V1∪V2∪{r} and E=E1∪E2∪{(r,r1),(r,r2)}. If root-label equivalence is required, an equivalence check may be performed before deciding whether to create a new root or to merge r1 and r2 directly. If a new root is used, properties such as edge directions and node labels must be updated to maintain consistency.

Applications and considerations. MergeRoots is useful when combining independent hierarchical analyses, aligning tree-structured data from different sources, or preparing unified inputs for downstream processing. It is important to consider semantic compatibility, potential redundancy among combined subtrees, and the impact on traversal algorithms that assume a single coherent root. Complexity is typically linear in the total size of the input trees, with additional space for the new root.