We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Move Sub-Tree of N-Ary Tree

Number: 1655

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given the root of an N-ary tree with unique values and two nodes, p and q, adjust the tree by “moving” the entire subtree rooted at p so that it becomes a direct child of q (as its last child). If p is already an immediate child of q, no change is needed. Special care must be taken when q is in the subtree of p because simply attaching p under q would create a cycle and disconnect part of the tree. In that case the tree must be “reconnected” appropriately so that all nodes remain in one tree. The problem asks you to return the root of the updated tree.

Key Insights

  • Use DFS (or recursion) to traverse the tree and locate parent pointers for nodes p and q.
  • Check if p is already a direct child of q – if so, return the tree unchanged.
  • Detect whether q is a descendant of p. If not (cases 2 or 3), you can simply detach p from its current parent and append it to q’s children.
  • If q is in p’s subtree (case 1), simply removing p may disconnect a part of the tree. In that situation, first detach q from its current parent within p’s subtree and reattach that branch to p’s original parent (or, if p is the root, make q the new root) to preserve connectivity, then finally attach p as a child of q.
  • The challenge is to carefully “cut” and “paste” the subtrees while avoiding cycles and ensuring that every node is still reachable in the final tree.

Space and Time Complexity

Time Complexity: O(n) – In the worst case, multiple DFS traversals (to find parents and check descendant relationships) may visit all n nodes. Space Complexity: O(n) – The recursion stack (or auxiliary data structures) may use up to O(n) space in the worst case.

Solution

We can solve the problem by performing a DFS to locate the parent of any given node. Two helper functions are used:

  1. findParent(root, target): Returns the parent of target by traversing the tree.
  2. isDescendant(root, target): Checks if target is in the subtree rooted at root.

The main function first checks whether p is already an immediate child of q and returns immediately if that is the case. Otherwise, it distinguishes two main scenarios: • When q is not a descendant of p (cases 2 and 3): detach p from its current parent and append it as the last child of q. • When q is in the subtree of p (case 1): this reattachment would create a cycle, so we must “disconnect” q from its current parent (within p’s subtree) and then reconnect that branch to p’s former parent (or, if p is the root, set q as the new root) so that the overall tree remains connected, before finally making p a child of q. The careful handling of parent pointers ensures that no node is lost and no cycle is formed during the process.

Code Solutions

Below are code solutions with detailed, line-by-line comments in Python, JavaScript, C++, and Java.

# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.children = []  # list of child nodes

# Helper function: Finds and returns the parent of the target node.
def findParent(root, target):
    # if root is None or has no children, no parent is found
    if not root or not root.children:
        return None
    # iterate over all children of the current root
    for child in root.children:
        # if the child is the target, current root is the parent
        if child == target:
            return root
        # otherwise, search recursively in the child’s subtree
        parent = findParent(child, target)
        if parent:
            return parent
    return None

# Helper function: Determines if 'target' is in the subtree rooted at 'root'.
def isDescendant(root, target):
    if root == target:
        return True
    for child in root.children:
        if isDescendant(child, target):
            return True
    return False

def moveSubtree(root, p, q):
    # Case: if p is already an immediate child of q, then no move is necessary.
    parOfP = None if root == p else findParent(root, p)
    if parOfP and parOfP == q:
        return root

    # Check if q is in the subtree of p.
    if not isDescendant(p, q):
        # Case 2 or 3: q is not a descendant of p.
        if parOfP:
            # Detach p from its current parent's children list.
            parOfP.children.remove(p)
        # Attach p as the last child of q.
        q.children.append(p)
        return root
    else:
        # Case 1: q is in the subtree of p.
        # This requires reconnecting the tree to avoid cycles.
        # If p is the root, then removing it disconnects the tree.
        if root == p:
            # Find the parent of q within p's subtree.
            parOfQ = findParent(p, q)
            # Detach q from its current parent to break the cycle.
            if parOfQ:
                parOfQ.children.remove(q)
            # Make q the new root.
            # Then attach p as a child of q (p’s subtree remains intact except the cut branch).
            q.children.append(p)
            return q  # New root is q.
        else:
            # p is not the root.
            # Find parent of q within p’s subtree.
            parOfQ = findParent(p, q)
            # Remove p from its current parent.
            parOfP.children.remove(p)
            # Detach q from its parent in p’s subtree.
            if parOfQ:
                parOfQ.children.remove(q)
            # Reconnect the branch: attach q as a new child of p's original parent.
            parOfP.children.append(q)
            # Finally, attach p as the last child of q.
            q.children.append(p)
            return root

# You can test the solution by constructing an N-ary tree using Node objects and calling moveSubtree.
← Back to All Questions