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.

Description Hints 3 Video 28:50

1516. Move Sub-Tree of N-Ary Tree

Hard59.7% acceptance1 companyPremium elsewhere, free here

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:

Node q is in the sub-tree of node p.
Node p is in the sub-tree of node q.
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).

Asked at 1 company

Google

Topics

Depth-First Search Tree

Hints open one at a time

Hint 1

Disconnect node p from its parent and append it to the children list of node q.

Hint 2

If q was in the sub-tree of node p (case 1), get the parent node of p and replace p in its children list with q.

Hint 3

If p was the root of the tree, make q the root of the tree.