Move Sub-Tree of N-Ary Tree

Problem

Given the root of an N-ary tree of unique values, and two nodes of the tree p and q.

You should move the subtree of the node p to become a direct child of node q. If p is already a direct child of q, do not change anything. Node p must be the last child in the children list of node q.

Return the root of the tree after adjusting it.

There are 3 cases for nodes p and q:

1. Node q is in the sub-tree of node p.
2. Node p is in the sub-tree of node q.
3. Neither node p is in the sub-tree of node q nor node q is in the sub-tree of node p.

In cases 2 and 3, you just need to move p (with its sub-tree) to be a child of q, but in case 1 the tree may be disconnected, thus you need to reconnect the tree again. Please read the examples carefully before solving this problem.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

For example, the above tree is serialized as [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14].

Examples

Example 1:


Input: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 4, q = 1
Output: [1,null,2,3,4,null,5,null,6,null,7,8]
Explanation: This example follows the second case as node p is in the sub-tree of node q. We move node p with its sub-tree to be a direct child of node q.
Notice that node 4 is the last child of node 1.

Example 2:


Input: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 7, q = 4
Output: [1,null,2,3,null,4,5,null,6,null,7,8]
Explanation: Node 7 is already a direct child of node 4. We don't change anything.

Example 3:


Input: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 3, q = 8
Output: [1,null,2,null,4,5,null,7,8,null,null,null,3,null,6]
Explanation: This example follows case 3 because node p is not in the sub-tree of node q and vice-versa. We can move node 3 with its sub-tree and make it as node 8's child.

Constraints:

• The total number of nodes is between [2, 1000].
• Each node has a unique value.
• p != null
• q != null
• p and q are two different nodes (i.e. p != q).

Solution

Method 1 - DFS + Parent Mapping

Intuition

We need to move the subtree rooted at node p to be the last child of node q. The main challenge is handling the case when q is in the subtree of p, which can disconnect the tree. We use DFS to build parent and node maps, then carefully rewire the tree according to the problem's cases.

Approach

1. Traverse the tree to build maps from value to node and from node to parent.
2. Check if p is already a child of q. If so, do nothing.
3. If q is in the subtree of p, moving p under q would disconnect the tree. We must reattach the part above q to maintain connectivity.
4. Otherwise, remove p from its current parent and add it as the last child of q.

Code

Java

class Node {
    public int val;
    public List<Node> children;
    public Node(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
}

public Node moveSubTree(Node root, Node p, Node q) {
    Map<Node, Node> parent = new HashMap<>();
    dfs(root, null, parent);
    if (parent.get(p) == q) return root; // already child
    // Check if q is in p's subtree
    if (isDescendant(p, q)) {
        Node qParent = parent.get(q);
        // Remove q from its parent
        if (qParent != null) {
            qParent.children.remove(q);
        }
        // Remove p from its parent
        parent.get(p).children.remove(p);
        // Add p as last child of q
        q.children.add(p);
        // Add q as child of p's old parent
        if (parent.get(p) != null) {
            parent.get(p).children.add(q);
        } else {
            root = q;
        }
    } else {
        // Remove p from its parent
        parent.get(p).children.remove(p);
        // Add p as last child of q
        q.children.add(p);
    }
    return root;
}

private void dfs(Node node, Node par, Map<Node, Node> parent) {
    if (node == null) return;
    parent.put(node, par);
    for (Node child : node.children) {
        dfs(child, node, parent);
    }
}

private boolean isDescendant(Node p, Node q) {
    if (p == q) return true;
    for (Node child : p.children) {
        if (isDescendant(child, q)) return true;
    }
    return false;
}

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def moveSubTree(root: 'Node', p: 'Node', q: 'Node') -> 'Node':
    parent = {}
    def dfs(node, par):
        parent[node] = par
        for child in node.children:
            dfs(child, node)
    dfs(root, None)
    if parent[p] == q:
        return root
    def is_descendant(a, b):
        if a == b:
            return True
        return any(is_descendant(child, b) for child in a.children)
    if is_descendant(p, q):
        q_parent = parent[q]
        if q_parent:
            q_parent.children.remove(q)
        parent[p].children.remove(p)
        q.children.append(p)
        if parent[p]:
            parent[p].children.append(q)
        else:
            root = q
    else:
        parent[p].children.remove(p)
        q.children.append(p)
    return root

Complexity

• ⏰ Time complexity: O(n) — Each node is visited at most twice (DFS and rewiring).
• 🧺 Space complexity: O(n) — For parent mapping and recursion stack.