Move sub tree of n ary tree

Tree Depth-First Search

59.6% acceptance

Mar 31, 2026

Given the root of an N-ary tree 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, do not 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: Node q is in the sub-tree of node p. Node p is in the sub-tree of node q. 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). 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].

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

/*
// Definition for a Node.
class Node {
public:
  int val;
  vector<Node*> children;

  Node() {}

  Node(int _val) {
    val = _val;
  }

  Node(int _val, vector<Node*> _children) {
    val = _val;
    children = _children;
  }
};
*/

class Solution {
public:
  Node* moveSubTree(Node* root, Node* p, Node* q) {
    // Check if p is already a direct child of q
    for (auto child : q->children) {
      if (child == p) return root;
    }
    
    // Check if q is in the subtree of p
    bool qUnderP = isDescendant(p, q);
    
    // Find parent of p and parent of q
    Node dummy(0, {root});
    Node* parentP = findParent(&dummy, p);
    
    // Remove p from its parent's children, remember position
    auto& pc = parentP->children;
    auto it = find(pc.begin(), pc.end(), p);
    int pos = it - pc.begin();
    pc.erase(it);
    
    // If q is under p, we need to reconnect
    if (qUnderP) {
      // Find parent of q within p's subtree
      Node* pqParent = findParent(p, q);
      auto& pqc = pqParent->children;
      pqc.erase(find(pqc.begin(), pqc.end(), q));
      // Insert q at the same position where p was
      pc.insert(pc.begin() + pos, q);
    }
    
    // Add p as last child of q
    q->children.push_back(p);
    
    return dummy.children[0];
  }
  
private:
  bool isDescendant(Node* root, Node* target) {
    if (root == target) return true;
    for (auto child : root->children) {
      if (isDescendant(child, target)) return true;
    }
    return false;
  }
  
  Node* findParent(Node* root, Node* target) {
    for (auto child : root->children) {
      if (child == target) return root;
      Node* res = findParent(child, target);
      if (res) return res;
    }
    return nullptr;
  }
};