Taro Logo

Move Sub-Tree of N-Ary Tree

Hard
Asked by:
Profile picture
46 views
Topics:
TreesRecursion

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:

  1. Find the node named nodeP with value p and the node named nodeQ with value q.
  2. Save the subtree rooted at nodeP.
  3. Remove the node nodeP from its original parent.
  4. Make the subtree rooted at 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:

  • If node p does not exist in the tree, do nothing.
  • If node q does not exist in the tree, do nothing.
  • You can assume that the given tree is valid.
  • 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:

  • The number of nodes in the tree is in the range [1, 1000].
  • 1 <= Node.val <= 1000
  • All node values are distinct.
  • p != q

Solution


Clarifying Questions

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

  1. Can the node values in the N-ary tree be any data type, and are they guaranteed to be unique?
  2. If either the source or destination node is not found in the tree, what should the function return or do?
  3. Is it possible for the source node to be an ancestor of the destination node? If so, how should the move be handled?
  4. Are we guaranteed that the source node is not the root of the entire tree? If it is, is the destination node allowed to be a descendant of the source node?
  5. Should the function modify the input tree in place, or should it return a new modified tree while leaving the original unchanged?

Brute Force Solution

Approach

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:

  1. Pick the subtree that we want to move.
  2. Consider each node in the entire tree (except the subtree we are moving) as a potential new parent for the subtree.
  3. For each potential parent, check if moving the subtree to that parent would break the tree's rules (e.g., creating cycles or placing a node as its own child).
  4. If moving the subtree to the potential parent is valid, then move the subtree to that location and declare that we found the solution.
  5. If we have tried every possible parent and haven't found a valid location, then it's impossible to move this subtree, so there is no solution.

Code Implementation

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 False

Big(O) Analysis

Time Complexity
O(n²) – The algorithm iterates through each of the n nodes in the tree to consider them as potential new parents for the subtree being moved. For each of these n potential parents, it must validate if the move is valid, which involves checking for cycles and other rule violations, potentially requiring traversal of the subtree (which can be at most n nodes in the worst case). Therefore, in the worst-case scenario, we are performing validation operations that could take O(n) time for each of the n potential parent nodes. This results in approximately n * n operations, which simplifies to O(n²).
Space Complexity
O(1) – The described brute force algorithm iterates through all nodes in the tree to find a potential new parent for the subtree being moved. It checks the validity of each potential move in place without needing to store any additional data structures that scale with the input size N, where N is the number of nodes in the tree. Therefore, the algorithm uses constant auxiliary space. No significant temporary lists, hash maps, or recursion stack frames are created.

Optimal Solution

Approach

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

  1. First, find the sub-tree you want to move and the node where you want to move it to.
  2. Next, disconnect the sub-tree from its current parent node. This involves removing the sub-tree from the parent's list of children.
  3. Then, carefully update the parent of the sub-tree being moved to now be the target node where it should be re-attached.
  4. Now, add the sub-tree as a child of the target node.
  5. Finally, if the destination node used to be part of the moved subtree, make sure to handle this case correctly to avoid creating a loop in the tree, potentially by moving the destination node as well.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n) – Finding the subtree and target node involves traversing the tree, which in the worst case visits all n nodes once. Disconnecting the subtree from its parent involves searching the parent's children list, which takes O(k) where k is the number of children of that parent. In the worst case, k can approach n (if one node has all others as children). Updating the parent and adding the subtree as a child of the target node are constant time operations O(1). Checking for and handling cycles also involves traversing a part of the tree which in worst case can be O(n). Thus, the overall time complexity is dominated by tree traversals and searching the parent's children list, resulting in O(n).
Space Complexity
O(H) – The algorithm's space complexity is primarily determined by the depth of the recursive calls if the finding or moving operations use recursion to traverse the tree. In the worst-case scenario, the recursion depth can be equal to the height (H) of the N-ary tree, with each recursive call adding a new frame to the call stack. Therefore, the auxiliary space used is proportional to the height of the tree. The input size N (number of nodes) can influence the height of the tree, but the direct relationship is more closely tied to H, which can range from log(N) to N depending on the tree's balance.

Edge Cases

Null root node
How to Handle:
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
How to Handle:
Return without modifying the tree, or throw an exception based on requirements.
Moving the root node
How to Handle:
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
How to Handle:
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
How to Handle:
Avoid redundant operation and return without making any changes.
Large depth N-ary Tree
How to Handle:
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
How to Handle:
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)
How to Handle:
Test with a large subtree to ensure the move operation is efficient and doesn't time out or consume excessive memory.