You are given the root of an N-ary tree and two integers, p and q.
Your task is to move the subtree rooted at the node with the value p to become a subtree of the node with the value q.
Specifically, you need to:
nodeP with value p and the node named nodeQ with value q.nodeP.nodeP from its original parent.nodeP become a child of nodeQ.A node can have multiple children. You should insert the subtree as the last child.
Return the root of the tree after performing the move operation.
Note:
p does not exist in the tree, do nothing.q does not exist in the tree, do nothing.p and q are distinct.Example 1:
Input: root = [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], p = 2, q = 4 Output: [1,null,4,3,5,null,null,2,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Explanation: - Node 2's original parent is node 1, and node 4 is node 1 as well. - Move the subtree rooted at node 2 to be the last child of node 4.
Example 2:
Input: root = [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], p = 2, q = 7 Output: [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] Explanation: Node 7 is in the subtree rooted at node 2, so you need to move node 2 to node 7. However, you cannot move a node to one of its descendants.
Example 3:
Input: root = [1,2,null,3,null,4,null,5,null,6,null], p = 3, q = 2 Output: [1,2,null,4,null,5,null,6,null]
Constraints:
[1, 1000].1 <= Node.val <= 1000p != qWhen you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force way to move a piece of our tree involves trying every single possible place we can move it to. We check if moving it to each possible location is valid according to the tree's rules, and if it is, we do it. If we find a valid move, we stop, otherwise we keep trying.
Here's how the algorithm would work step-by-step:
class NAryNode:
def __init__(self, value):
self.value = value
self.children = []
def move_subtree_brute_force(root, subtree_root, new_parent):
if subtree_root == root:
return False
subtree_nodes = get_all_nodes(subtree_root)
all_nodes = get_all_nodes(root)
for potential_parent in all_nodes:
if potential_parent in subtree_nodes:
continue
original_parent = find_parent(root, subtree_root)
if original_parent:
original_parent.children = [child for child in original_parent.children if child != subtree_root]
else:
root = None
# Check if moving creates a cycle
if not is_valid_move(subtree_root, potential_parent):
if original_parent:
original_parent.children.append(subtree_root)
else:
root = subtree_root
continue
potential_parent.children.append(subtree_root)
return True
return False
def get_all_nodes(root):
if not root:
return []
nodes = [root]
for child in root.children:
nodes.extend(get_all_nodes(child))
return nodes
def find_parent(root, node_to_find):
if not root or root == node_to_find:
return None
for child in root.children:
if child == node_to_find:
return root
parent = find_parent(child, node_to_find)
if parent:
return parent
return None
def is_valid_move(subtree_root, potential_parent):
# Check if moving would create a cycle
if is_ancestor(subtree_root, potential_parent):
return False
return True
def is_ancestor(node, potential_ancestor):
if not node:
return False
if node == potential_ancestor:
return True
for child in node.children:
if is_ancestor(child, potential_ancestor):
return True
return FalseTo move a sub-tree within an N-ary tree efficiently, we detach the sub-tree from its original location and then attach it to the desired new location. We do this by updating the connections between nodes in a way that preserves the overall tree structure without causing loops.
Here's how the algorithm would work step-by-step:
class Node:
def __init__(self, value):
self.value = value
self.children = []
def move_subtree(root, subtree_to_move, destination_node):
if not root or not subtree_to_move or not destination_node:
return
# Find the parent of the subtree to move
parent_of_subtree = find_parent(root, subtree_to_move)
if parent_of_subtree:
# Disconnect subtree from its current parent
parent_of_subtree.children = [child for child in parent_of_subtree.children if child != subtree_to_move]
# Check if the destination is within the subtree to be moved
if is_ancestor(subtree_to_move, destination_node):
# Avoid creating a cycle in the tree.
original_destination_parent = find_parent(root, destination_node)
if original_destination_parent:
original_destination_parent.children = [child for child in original_destination_parent.children if child != destination_node]
subtree_to_move.children.append(destination_node)
# Update the parent of the subtree
subtree_to_move.parent = destination_node
# Add the subtree to the destination node's children
destination_node.children.append(subtree_to_move)
def find_parent(root, node_to_find):
if not root or root == node_to_find:
return None
queue = [root]
while queue:
current_node = queue.pop(0)
for child in current_node.children:
if child == node_to_find:
return current_node
queue.append(child)
return None
def is_ancestor(potential_ancestor, node):
if not potential_ancestor or not node:
return False
if potential_ancestor == node:
return True
queue = [potential_ancestor]
while queue:
current_node = queue.pop(0)
if current_node == node:
return True
queue.extend(current_node.children)
return False| Case | How to Handle |
|---|---|
| Null root node | Return null or perform no action if the root node is null as there is no tree to modify. |
| Null node to move or null new parent node | Return without modifying the tree, or throw an exception based on requirements. |
| Moving the root node | Update the tree's root to the new parent's root, handling root pointer changes correctly. |
| Moving a node to be a child of itself or a descendant | Prevent cycles by checking if the new parent is within the subtree being moved and return an error, or no-op in this case. |
| Node to move is already a child of the new parent | Avoid redundant operation and return without making any changes. |
| Large depth N-ary Tree | Ensure the solution doesn't lead to stack overflow in recursive implementations, potentially using iterative approach with a queue/stack instead. |
| New parent already has the maximum number of children | Handle full parent by either rejecting the move, replacing an existing child based on priority, or resizing the children array dynamically. |
| Moving a large subtree (many nodes) | Test with a large subtree to ensure the move operation is efficient and doesn't time out or consume excessive memory. |