# Share my accepted recursive solution with comments - Java

• The idea is very simple:

1. flatten left subtree

2. flatten right subtree

3. concatenate root -> left flatten subtree -> right flatten subtree

`````` public void flatten(TreeNode root) {
if(root == null)
return;

flatten(root.left);
flatten(root.right);

// save current right for concatination
TreeNode right = root.right;

if(root.left != null) {

// step 1: concatinate root with left flatten subtree
root.right = root.left;
root.left = null; // set left to null

// step 2: move to the end of new added flatten subtree
while(root.right != null)
root = root.right;

// step 3: contatinate left flatten subtree with flatten right subtree
root.right = right;
}
}``````

• I think the time complexity of your code is greater than O(n). Due to step 2: move to the end of new added flatten subtree, it takes more than O(1) to move to the end, and concatenate root -> left flatten subtree -> right flatten subtree.

• Oh, I am wrong. I see that. The time complexity is still O(n). If we consider the while loop separately, the total time spent in while loop is n / 2 + n / 4 + ... + 1 = O(n). Besides the while loop, it takes O(n) to visit each node and do the modification of children stuff. Thus, the total time complexity is O(n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.