Move Sub-Tree of N-Ary Tree - Solution & Explanation

Problem Overview: You are given the root of an N-ary tree and two nodes p and q. The task is to move the entire subtree rooted at p so it becomes a child of q. The tricky part appears when q already lies inside the subtree of p. In that case, directly attaching p under q would create a cycle, so the tree structure must be carefully rearranged.

Approach 1: Repeated Tree Traversal (Brute Force) (O(n^2) time, O(n) space)

The straightforward idea is to repeatedly traverse the tree to locate parent nodes and subtree relationships. First, run a DFS to find the parent of p and detach it. Then traverse again to check whether q lies inside p's subtree. If it does, locate q's parent and adjust the pointers so the structure remains a valid tree. Because each structural change may require another full traversal, the algorithm can degrade to O(n^2) time in the worst case. This method works but performs unnecessary scans across the tree.

Approach 2: Parent Mapping + DFS (Optimal) (O(n) time, O(n) space)

The efficient solution performs a single depth-first search to build a parent map for every node in the tree. With this map, you can access and update parent-child relationships in constant time. After the DFS, check whether q exists inside the subtree rooted at p. This check can be done with another targeted DFS starting at p.

If q is not in p's subtree, the operation is simple: remove p from its parent's children list and append it to q's children. If q is inside the subtree of p, the structure must rotate: remove q from its parent, replace p with q in p's parent children list, and finally attach p as a child of q. Because the parent relationships are already stored, each modification becomes a constant-time operation.

This approach relies heavily on efficient traversal of a tree structure and pointer updates rather than repeated searches. The entire tree is processed once to build the parent map and once more for the subtree check, resulting in overall O(n) time and O(n) space.

Recommended for interviews: The parent-map DFS approach. Interviewers want to see that you understand subtree relationships and how to safely rewire nodes in a tree without breaking its structure. Mentioning the brute force traversal shows awareness of the naive path, but implementing the O(n) DFS solution demonstrates stronger control over tree manipulation and graph-style parent tracking.