# An inorder python solution

• ``````class Solution:
# @param root, a tree node
# @return nothing, do it in place
prev = None
def flatten(self, root):
if not root:
return
self.prev = root
self.flatten(root.left)

temp = root.right
root.right, root.left = root.left, None
self.prev.right = temp

self.flatten(temp)

*
/
n
/     \
left   right
\
*
*
\
p
``````

The idea is very simple. Suppose n is the current visiting node, and p is the previous node of preorder traversal to n.right.

We just need to do the inorder replacement:

n.left -> NULL

n.right - > n.left

p->right -> n.right

• I think this is a very smart method. i was wondering how to solve this problem recursively and didn't know how to return the 'prev'. very helpful, thanks a lot.

• I think there is no need to pass prev. See my code and embedded comments

``````class Solution:
# @param {TreeNode} root
# @return {void} Do not return anything, modify root in-place instead.
def flatten(self, root):
'''
1. flatten left subtree
2. find left subtree's tail
3. set root's left to None, root's right to root'left, tail's right to root.right
4. flatten the original right subtree
'''
# escape condition
if not root:
return
right = root.right
if root.left:
# flatten left subtree
self.flatten(root.left)
# find the tail of left subtree
tail = root.left
while tail.right:
tail = tail.right
# left <-- None, right <-- left, tail's right <- right
root.left, root.right, tail.right = None, root.left, right
# flatten right subtree
self.flatten(right)``````

• @dasheng2

```while tail.right:
tail = tail.right
```

this code will loop over left subtree, which waste a lot of time

• @julian3
Hi Julian, I am a little bit confused about how do you get self.prev to the end of left side.

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