LeetCode 1516: Move Sub-Tree of N-Ary Tree Solution
Master LeetCode problem 1516 (Move Sub-Tree of N-Ary Tree), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1516. Move Sub-Tree of N-Ary Tree
Problem Explanation
Explanation:
To move a subtree within an N-ary tree, we need to identify the subtree to be moved along with its parent node. Once we have this information, we detach the subtree from its current parent and attach it to the new parent node.
The steps involved in the algorithm are as follows:
- Find the subtree to be moved and its parent node.
- Detach the subtree from its current parent.
- Attach the subtree to the new parent node.
Time Complexity:
The time complexity of this algorithm is O(n), where n is the number of nodes in the N-ary tree.
Space Complexity:
The space complexity of this algorithm is O(1) since we are not using any additional data structures that grow with the input size.
:
Solution Code
class Solution {
public Node moveSubTree(Node root, Node p, Node q) {
if (p.equals(q)) return root;
if (isDescendant(p, q)) return root;
Node parentP = findParent(root, p);
if (parentP == null) return root;
if (parentP.equals(q)) {
if (q.children == null) q.children = new ArrayList<>();
q.children.add(p);
detachChild(parentP, p);
return q;
}
detachChild(parentP, p);
if (q.children == null) q.children = new ArrayList<>();
q.children.add(p);
return root;
}
private boolean isDescendant(Node p, Node q) {
if (p.equals(q)) return true;
if (p.children == null) return false;
for (Node child : p.children) {
if (isDescendant(child, q)) return true;
}
return false;
}
private Node findParent(Node node, Node target) {
if (node.children != null) {
for (Node child : node.children) {
if (child.equals(target)) return node;
Node parent = findParent(child, target);
if (parent != null) return parent;
}
}
return null;
}
private void detachChild(Node parent, Node child) {
parent.children.remove(child);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1516 (Move Sub-Tree of N-Ary Tree)?
This page provides optimized solutions for LeetCode problem 1516 (Move Sub-Tree of N-Ary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1516 (Move Sub-Tree of N-Ary Tree)?
The time complexity for LeetCode 1516 (Move Sub-Tree of N-Ary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1516 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1516 in Java, C++, or Python.