Skip to main content
Talentd

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

HardPremiumFree on FleetCodeTreeDepth-First Search5 min readAsked at: Google
Practice this problem

Problem Statement

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].

 

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.

Example 4:

Input: root = [1,null,2,3,null,4], p = 1, q = 4
Output: [4,null,1,null,2,3]
Explanation: This example follows case 1 because node q is in the sub-tree of node p. Disconnect 4 with its parent and move node 1 with its sub-tree and make it as node 4'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).

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Traversal (Brute Force)O(n^2)O(n)Conceptual understanding or quick prototype when constraints are small
Parent Map + DFSO(n)O(n)General case; efficient tree restructuring with constant-time parent lookups

Video Solution

1516. Move Sub-Tree of N-Ary Tree (Leetcode Hard) • Programming Live with Larry • 215 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Move Sub-Tree of N-Ary Tree easy or hard?
Move Sub-Tree of N-Ary Tree is categorized as a Hard problem because it requires careful handling of edge cases where q lies inside p's subtree. Correctly updating multiple parent-child relationships without creating cycles makes the problem more complex than typical tree traversal questions.
Move Sub-Tree of N-Ary Tree Python/Java solution
Implement a DFS to store parent pointers in a dictionary or map. After identifying the relationship between p and q, update the parent children lists accordingly. The same logic works across Python, Java, C++, and Go because it only requires DFS traversal and list manipulation.
How to solve Move Sub-Tree of N-Ary Tree in O(n)?
Run a DFS to record each node's parent. Then check if q exists in the subtree rooted at p. If not, detach p from its parent and append it to q's children. If q is inside p's subtree, detach q, replace p with q in p's parent, and attach p under q. All updates become constant-time operations after the initial DFS.
What is the best approach for Move Sub-Tree of N-Ary Tree?
The best approach uses depth-first search to build a parent map for all nodes, then updates parent-child relationships in constant time. This allows you to detect whether q lies inside p's subtree and adjust the structure accordingly. The method runs in O(n) time and O(n) space.
Is Move Sub-Tree of N-Ary Tree asked at Google/Amazon/Meta?
Tree restructuring and pointer manipulation problems are common in interviews at companies like Google, Amazon, and Meta. Variations of subtree movement, tree rotations, and parent-child rewiring frequently appear in system design and data structure rounds.
What data structure is used in Move Sub-Tree of N-Ary Tree?
The core data structure is an N-ary tree combined with a hash map that stores parent references for each node. Depth-first search is used to traverse the tree and populate this mapping before performing structural updates.
What is the time complexity of Move Sub-Tree of N-Ary Tree?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. One DFS builds the parent mapping and another traversal checks if q lies in p's subtree. Space complexity is O(n) due to the parent map and recursion stack.

Ready to solve this problem?

Practice Move Sub-Tree of N-Ary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Root of N-Ary Tree