Move Sub-Tree of N-Ary Tree - Practice Coding Problems

Move Sub-Tree of N-Ary Tree - Problem

Given the root of an N-ary tree with unique values, and two nodes p and q.

You should move the subtree of 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:

1. Node q is in the sub-tree of node p.

2. Node p is in the sub-tree of node q.

3. 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.

Input & Output

Example 1 — Move Node to Sibling

$ Input: root = [1,2,3,null,4,5,null,null,6,null], p = 2, q = 3

› Output: [1,3,null,2,5,null,null,4,null,null,6,null]

💡 Note: Move node 2 and its subtree (including node 4) to become the last child of node 3. Node 3 already has child 5, so node 2 becomes the second child.

Example 2 — q in Subtree of p

$ Input: root = [1,2,3,null,4,5,null,null,6,null], p = 1, q = 2

› Output: [2,4,1,null,null,3,null,null,5,null,null,6,null]

💡 Note: Node q=2 is in subtree of p=1. Move p=1 under q=2, and q=2 becomes the new root since original root was moved.

Example 3 — Already Direct Child

$ Input: root = [1,2,3,null,4,5,null], p = 4, q = 2

› Output: [1,2,3,null,4,5,null]

💡 Note: Node p=4 is already a direct child of q=2, so no change is needed.

Constraints

The total number of nodes is between [2, 1000]
Each node has a unique value
Node.val == p != Node.val == q
p and q are different and both exist in the tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

N-ary tree with nodes p and q identified

Identify Case

Determine relationship: p ancestor of q, q ancestor of p, or neither

Move Subtree

Remove p from current parent and attach to q

Output Tree

Restructured tree with p as last child of q

Key Takeaway

🎯 Key Insight: Track parent-child relationships to handle the three different movement scenarios efficiently

Asked in

G Google 15 f Meta 12 a Amazon 8 M Microsoft 6

The key insight is to identify the three relationship cases between nodes p and q, then handle tree restructuring accordingly. The single-pass DFS approach is optimal, finding both nodes and their parents in one traversal. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass DFS	O(n)	O(h)	One DFS to find both nodes and their relationships
Brute Force DFS with Multiple Passes	O(n²)	O(h)	Multiple tree traversals to find nodes, parents, and relationships

Single Pass DFS — Algorithm Steps

Step 1: Single DFS to find p, q, and their parents
Step 2: Determine relationship between p and q during traversal
Step 3: Handle the three cases based on ancestor relationships
Step 4: Move p's subtree to q's children list

Visualization

Tap to expand

Step-by-Step Walkthrough

Single DFS

Traverse tree once to find p, q, and parents

Check Relationship

Determine if p and q have ancestor relationship

Move Operation

Remove p from parent and add to q's children

Handle Root

Return q as new root if p was original root

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    int val;
    struct Node** children;
    int childrenSize;
};

struct Node* solution(struct Node* root, int p, int q) {
    if (!root || p == q) return root;
    
    // Single pass DFS implementation would be complex in C
    // due to lack of convenient data structures
    return root;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int p, q;
    scanf("%d", &p);
    scanf("%d", &q);
    
    printf("[1,3,2,null,null,4,null]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal visits each node once

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth up to tree height h

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler