# 1516. Move Sub-Tree of N-Ary Tree

<https://leetcode.com/problems/move-sub-tree-of-n-ary-tree>

## Description

Given the `root` of an [N-ary tree](https://leetcode.com/articles/introduction-to-n-ary-trees/) 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`, don't 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).*

![](https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png)

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:**

![](https://assets.leetcode.com/uploads/2020/07/13/move_e1.jpg)

```
**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:**

![](https://assets.leetcode.com/uploads/2020/07/13/move_e2.jpg)

```
**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:**

![](https://assets.leetcode.com/uploads/2020/07/13/move_e3.jpg)

```
**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:**

![](https://assets.leetcode.com/uploads/2020/07/13/move_e4.jpg)

```
**Input:** root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 2, q = 7
**Output:** [1,null,7,3,null,2,null,6,null,4,5,null,null,8]
**Explanation:** Node q is in the sub-tree of node p, so this is case 1.
The first step, we move node p (with all of its sub-tree except for node q) and add it as a child to node q.
Then we will see that the tree is disconnected, you need to reconnect node q to replace node p as shown.
```

**Example 5:**

![](https://assets.leetcode.com/uploads/2020/07/13/move_e5.jpg)

```
**Input:** root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 1, q = 2
**Output:** [2,null,4,5,1,null,7,8,null,null,3,null,null,null,6]
**Explanation:** Node q is in the sub-tree of node p, so this is case 1.
The first step, we move node p (with all of its sub-tree except for node q) and add it as a child to node q.
As node p was the root of the tree, node q replaces it and becomes the root of the tree.
```

**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`).

## ac

```java
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/1516-move-sub-tree-of-n-ary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.