HardNo. 1516LeetCode Premium
Move Sub-Tree of N-Ary Tree — LeetCode 1516 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 4, q = 1
- Output
- [1,null,2,3,4,null,5,null,6,null,7,8]
- Explanation
- This example follows the second case as node p is in the sub-tree of node q. We move node p with its sub-tree to be a direct child of node q.
Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1516. Move Sub-Tree of N-Ary Tree is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0098 | Validate Binary Search Tree | Medium |
| 0099 | Recover Binary Search Tree | Medium |
| 0100 | Same Tree | Easy |
| 0101 | Symmetric Tree | Easy |
| 0104 | Maximum Depth of Binary Tree | Easy |
| 0110 | Balanced Binary Tree | Easy |
Frequently asked questions
- How hard is LeetCode 1516. Move Sub-Tree of N-Ary Tree?
LeetCode 1516. Move Sub-Tree of N-Ary Tree is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1516. Move Sub-Tree of N-Ary Tree?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1516. Move Sub-Tree of N-Ary Tree?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1516. Move Sub-Tree of N-Ary Tree cover?
LeetCode 1516. Move Sub-Tree of N-Ary Tree is tagged Tree and Depth-First Search on LeetCode.
- Is LeetCode 1516. Move Sub-Tree of N-Ary Tree a premium problem?
Yes. LeetCode 1516. Move Sub-Tree of N-Ary Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.