🎨Now live: Try our Free AI Image Generation Feature

Intuition
To flatten the tree, we need to rearrange its nodes such that the left subtree of each node is moved to the right, and the original right subtree is appended to the end of this new right subtree. The transformation should maintain the order of nodes as they would appear in a pre-order traversal.
Approach
- Traverse the tree using a pointer
curr
. - For each node, if there is a left subtree:
- Find the rightmost node in the left subtree (
runner
). - Attach the right subtree ofcurr
to the rightmost node in the left subtree. - Move the left subtree to the right and set the left toNone
. - Move
curr
to the right child. - Repeat until the entire tree is flattened.
Complexity
Time complexity:
O(n), where n is the number of nodes in the tree. Each node is visited once.
Space complexity:
O(1), as the solution uses a constant amount of extra space.
Code
C++
class Solution
{
public:
void flatten(TreeNode* root) {
TreeNode* curr = root;
while (curr) {
if (curr->left) {
TreeNode* runner = curr->left;
while (runner->right) {
runner = runner->right;
}
runner->right = curr->right;
curr->right = curr->left;
curr->left = nullptr;
}
curr = curr->right;
}
}
};
Python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
curr = root
while curr:
if curr.left:
runner = curr.left
while runner.right:
runner = runner.right
runner.right = curr.right
curr.right = curr.left
curr.left = None
curr = curr.right
Java
class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode runner = curr.left;
while (runner.right != null) {
runner = runner.right;
}
runner.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}
}
JavaScript
var flatten = function (root)
{
let curr = root
while (curr)
{
if (curr.left) {
let runner = curr.left
while (runner.right) runner = runner.right
runner.right = curr.right, curr.right = curr.left, curr.left = null
}
curr = curr.right
}
};