LeetCode 1516 - Move Sub-Tree of N-Ary Tree

LeetCode Problem 1516

Difficulty: 🔴 Hard
Topics: Tree, Depth-First Search

Solution

Problem Understanding

This problem asks us to modify the structure of an N-ary tree by moving one subtree under another node. Every node contains a unique value, and each node may have any number of children.

We are given:

• root, the root node of the N-ary tree
• p, the root of the subtree we want to move
• q, the node that should become the new parent of p

The operation is:

• Remove p from its current parent
• Attach p as the last child of q

At first glance, this sounds straightforward, but the difficulty comes from the relationship between p and q.

There are three possible structural relationships:

1. q is inside the subtree rooted at p
2. p is inside the subtree rooted at q
3. Neither node is inside the other’s subtree

Cases 2 and 3 are simple tree reattachment operations. We detach p from its parent and append it to q.children.

Case 1 is the tricky part. If q is already inside p’s subtree, then simply attaching p under q would create a cycle, which is invalid for a tree. To avoid this, we must first disconnect q from its current parent before moving p.

The constraints are relatively small:

• At most 1000 nodes
• All node values are unique

Because the tree is small, an O(n) traversal-based solution is completely acceptable.

Several edge cases are important:

• p may already be a direct child of q
• p may be the root
• q may be inside p’s subtree
• p and q may belong to unrelated branches
• Removing and reattaching nodes must never create cycles

A naive implementation often fails when q is inside p’s subtree because reconnecting the tree correctly requires careful handling of parent relationships.

Approaches

Brute Force Approach

A brute force solution would repeatedly traverse the tree whenever we need structural information.

For example:

• Traverse the tree to find the parent of p
• Traverse again to find the parent of q
• Traverse again to determine whether q lies inside p’s subtree
• Perform modifications afterward

This works because the tree is small, but it performs unnecessary repeated traversals.

The main drawback is that every operation requires additional DFS searches. Even though the total complexity is still acceptable for n <= 1000, the implementation becomes repetitive and harder to reason about.

Optimal Approach

The key insight is that tree modifications become much easier if we know every node’s parent.

We can perform one DFS traversal and build:

• A parent map: child -> parent
• An ancestor relationship checker using DFS

Once we know parent relationships, the subtree move becomes a sequence of local pointer updates.

The crucial observation is:

• If q is not inside p’s subtree, we can safely detach p and attach it under q
• If q is inside p’s subtree, we must first detach q from its current parent before attaching p under q

This prevents cycles and preserves tree connectivity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Multiple repeated traversals
Optimal	O(n)	O(n)	Single DFS plus constant-time structural updates

Algorithm Walkthrough

Step 1: Build Parent References

We perform a DFS traversal from the root and store:

parent[child] = current_node

This allows us to quickly:

• Remove a node from its parent
• Find the parent of any node in constant time

Without parent references, removing a subtree would require another traversal.

Step 2: Check Whether q Is Inside p’s Subtree

We run a DFS starting from p.

If we encounter q, then q belongs to p’s subtree.

This determines which structural case we are handling.

Step 3: Handle the Simple Case

If q is not inside p’s subtree:

1. Remove p from its current parent
2. Append p to q.children

This safely moves the subtree without affecting tree validity.

Step 4: Handle the Cycle Case

If q is inside p’s subtree:

1. Find q’s current parent
2. Remove q from that parent
3. Remove p from its parent if p is not the root
4. Attach p under q
5. Attach q into the position formerly occupied by p

This reconnects the tree correctly while avoiding cycles.

If p was the original root, then q becomes the new root.

Step 5: Return the Correct Root

Normally, the root stays unchanged.

However, when p was the root and q belonged to its subtree, q becomes the new root.

Why it works

The algorithm preserves the defining properties of a tree:

• Every node except the root has exactly one parent
• The structure remains connected
• No cycles are introduced

The only dangerous situation is attaching p under one of its descendants. By first disconnecting q from its original parent, we break the dangerous path that would otherwise create a cycle.

Because every modification is a valid tree edge replacement, the resulting structure is always a valid N-ary tree.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children if children is not None else []
"""

from typing import Optional, List

class Solution:
    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':

        parent = {}

        def build_parent(node: 'Node') -> None:
            for child in node.children:
                parent[child] = node
                build_parent(child)

        build_parent(root)

        # If p is already a direct child of q
        if p in q.children:
            return root

        def contains(node: 'Node', target: 'Node') -> bool:
            if node == target:
                return True

            for child in node.children:
                if contains(child, target):
                    return True

            return False

        q_in_p_subtree = contains(p, q)

        p_parent = parent.get(p)
        q_parent = parent.get(q)

        def remove_child(par: 'Node', child: 'Node') -> None:
            par.children.remove(child)

        if not q_in_p_subtree:
            # Case 2 or 3
            if p_parent:
                remove_child(p_parent, p)

            q.children.append(p)
            return root

        # Case 1

        # Remove q from its current parent
        if q_parent:
            remove_child(q_parent, q)

        # Remove p from its current parent
        if p_parent:
            p_index = p_parent.children.index(p)
            remove_child(p_parent, p)

            # Replace p with q
            p_parent.children.insert(p_index, q)

        # Attach p under q
        q.children.append(p)

        # If p was root, q becomes new root
        if root == p:
            return q

        return root

The implementation starts by building a parent map using DFS. This gives constant-time access to every node’s parent.

Next, the solution checks whether p is already a direct child of q. In that situation, the tree already satisfies the required structure, so no changes are necessary.

The helper function contains determines whether q belongs to p’s subtree. This distinction is critical because it tells us whether moving p directly would create a cycle.

For the normal cases, the implementation simply removes p from its current parent and appends it to q.children.

For the difficult case where q lies inside p’s subtree, the code carefully reconnects the tree:

• q is detached from its current parent
• p is removed from its parent
• q replaces p in the old parent’s child list
• p becomes a child of q

This preserves connectivity while avoiding cycles.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func moveSubTree(root *Node, p *Node, q *Node) *Node {

	parent := make(map[*Node]*Node)

	var buildParent func(*Node)

	buildParent = func(node *Node) {
		for _, child := range node.Children {
			parent[child] = node
			buildParent(child)
		}
	}

	buildParent(root)

	// If p is already a direct child of q
	for _, child := range q.Children {
		if child == p {
			return root
		}
	}

	var contains func(*Node, *Node) bool

	contains = func(node *Node, target *Node) bool {
		if node == target {
			return true
		}

		for _, child := range node.Children {
			if contains(child, target) {
				return true
			}
		}

		return false
	}

	qInPSubtree := contains(p, q)

	pParent := parent[p]
	qParent := parent[q]

	removeChild := func(par *Node, child *Node) {
		for i, c := range par.Children {
			if c == child {
				par.Children = append(par.Children[:i], par.Children[i+1:]...)
				return
			}
		}
	}

	if !qInPSubtree {

		if pParent != nil {
			removeChild(pParent, p)
		}

		q.Children = append(q.Children, p)

		return root
	}

	// Case 1

	if qParent != nil {
		removeChild(qParent, q)
	}

	if pParent != nil {

		pIndex := 0

		for i, child := range pParent.Children {
			if child == p {
				pIndex = i
				break
			}
		}

		removeChild(pParent, p)

		left := append([]*Node{}, pParent.Children[:pIndex]...)
		left = append(left, q)
		left = append(left, pParent.Children[pIndex:]...)

		pParent.Children = left
	}

	q.Children = append(q.Children, p)

	if root == p {
		return q
	}

	return root
}

The Go implementation follows the same algorithmic structure as the Python solution.

One important difference is slice manipulation. Go slices do not support direct removal like Python lists, so removing a child requires rebuilding the slice using append.

Another difference is map usage. The parent map uses pointers as keys:

map[*Node]*Node

This allows constant-time parent lookup using node identity.

Go also requires explicit nil checks instead of Python’s truthy checks.

Worked Examples

Example 1

Input:

root = [1,null,2,3,null,4,5,null,6,null,7,8]
p = 4
q = 1

Initial structure:

1
├── 2
└── 3
    ├── 4
    │   └── 6
    └── 5
        ├── 7
        └── 8

q = 1 is not inside p = 4’s subtree.

Operations:

Step	Action
1	Remove 4 from 3.children
2	Append 4 to 1.children

Final tree:

1
├── 2
├── 3
│   └── 5
│       ├── 7
│       └── 8
└── 4
    └── 6

Example 2

Input:

p = 7
q = 4

Current relationship:

4
└── 7

Since 7 is already a direct child of 4, the algorithm returns immediately.

No modifications occur.

Example 3

Input:

p = 3
q = 8

Initial structure:

1
├── 2
└── 3
    ├── 4
    │   └── 6
    └── 5
        ├── 7
        └── 8

8 is not inside 3’s subtree.

Operations:

Step	Action
1	Remove 3 from 1.children
2	Append 3 to 8.children

Final structure:

1
└── 2

8
└── 3
    ├── 4
    │   └── 6
    └── 5
        └── 7

Example 4

Input:

p = 1
q = 4

Initial structure:

1
├── 2
└── 3
    └── 4

Here, q = 4 is inside p = 1’s subtree.

Operations:

Step	Action
1	Remove 4 from 3.children
2	Attach 1 under 4
3	Since 1 was root, 4 becomes new root

Final structure:

4
└── 1
    ├── 2
    └── 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	DFS traversal plus constant-time structural operations
Space	O(n)	Parent map and recursion stack

The solution traverses the tree a constant number of times. Building the parent map requires O(n), and checking whether q lies inside p’s subtree also requires O(n) in the worst case.

All edge updates afterward are constant-time list operations relative to the node degree.

The auxiliary space comes from:

• The parent map
• DFS recursion stack

Both are linear in the number of nodes.

Test Cases

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def find(node, target):
    if node.val == target:
        return node

    for child in node.children:
        res = find(child, target)
        if res:
            return res

    return None

# Example 1
root = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

root.children = [n2, n3]
n3.children = [n4]

res = Solution().moveSubTree(root, n4, root)

assert root.children[-1] == n4  # moved under root

# Example 2
root = Node(1)
n2 = Node(2)

root.children = [n2]

res = Solution().moveSubTree(root, n2, root)

assert root.children[0] == n2  # already child

# Example 3
root = Node(1)
n2 = Node(2)
n3 = Node(3)
n8 = Node(8)

root.children = [n2, n3]
n3.children = [n8]

res = Solution().moveSubTree(root, n3, n8)

assert n8.children[-1] == n3  # moved to unrelated branch

# Example 4
root = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

root.children = [n2, n3]
n3.children = [n4]

res = Solution().moveSubTree(root, root, n4)

assert res == n4  # new root becomes q
assert n4.children[0] == root

# Single chain test
root = Node(1)
n2 = Node(2)
n3 = Node(3)

root.children = [n2]
n2.children = [n3]

res = Solution().moveSubTree(root, n2, n3)

assert res == root  # structure remains valid

# Unrelated branches
root = Node(1)
a = Node(2)
b = Node(3)
c = Node(4)

root.children = [a, b]
a.children = [c]

res = Solution().moveSubTree(root, c, b)

assert b.children[-1] == c  # moved across branches

Test	Why
Move subtree under ancestor	Validates normal reattachment
Already direct child	Ensures early return works
Move across unrelated branches	Validates case 3
Move root under descendant	Validates difficult cycle case
Single chain structure	Tests deep ancestor relationships
Cross-branch movement	Ensures parent updates are correct

Edge Cases

Moving the Root Under One of Its Descendants

This is the hardest case in the problem. If we directly attach the root under one of its descendants, the tree would contain a cycle.

For example:

1
└── 2
    └── 3

Moving 1 under 3 without disconnecting 3 first would produce:

1 -> 2 -> 3 -> 1

The implementation avoids this by first removing q from its parent before attaching p beneath it.

p Already Being a Child of q

A naive implementation might remove and reinsert the node unnecessarily, potentially changing child ordering or introducing subtle bugs.

The solution explicitly checks:

if p in q.children:
    return root

This guarantees no structural changes occur when the tree already satisfies the requirement.

Moving Between Unrelated Branches

When neither node is inside the other’s subtree, the operation should behave like a standard subtree move.

The main risk here is forgetting to detach p from its old parent, which would incorrectly leave the subtree attached in two places.

The implementation safely removes p before appending it to q.children, ensuring every node still has exactly one parent.