The Move Sub-Tree of N-Ary Tree problem gives you an N-ary tree (each node can have multiple children) and two node references p and q. Move the subtree rooted at p to become a child of q. If p is already a child of q, move it to be the last child. This hard Move Sub-Tree of N-Ary Tree coding problem requires careful parent tracking and edge cases around ancestor-descendant relationships.
Google asks this hard problem to test DFS on N-ary trees combined with edge case reasoning. The tricky case — when q is a descendant of p — requires detaching p from its parent first, then re-attaching. The depth-first search and tree interview pattern is the core, and the problem tests whether candidates can reason carefully about tree structure changes without corrupting the tree.
DFS for parent finding + careful re-attachment. First, find the parent of p and the parent of q using DFS. Handle the edge case: if q is a descendant of p, first detach p from its parent (replacing p in its parent's children list with p's children or handling accordingly), then make q's parent correct. Otherwise, simply detach p from its current parent, then add p as the last child of q.
Tree: root→[A, B, C]. A→[D, E]. Move subtree at A to become child of B.
Edge case: Move root's child B (with B→A) under A. A is a descendant of root but B is parent of A... handle carefully.
Tree restructuring problems require clearly separating the "find" phase from the "modify" phase. First, gather all necessary information (parent of p, parent of q, relationship between p and q). Then apply modifications. The ancestor check — "is q a descendant of p?" — is the critical invariant test. Practice DFS parent-tracking implementations on N-ary trees, as they differ slightly from binary tree restructuring in requiring iteration over children lists.
