# Recursive and non-recursive solutions in python

• Recursive one:

``````class Solution:
# @param root, a tree node
# @return nothing, do it in place
def flatten(self, root):
if not root:
return None
elif not (root.left or root.right):
return root
temp=root
while temp and (temp.left or temp.right):
if temp.left:
# flatten the left subtree if exist and return the end node
tmptail=self.flatten(temp.left)
# insert the flattened left subtree into the original tree. Then set the left child as None and update the temp.
temp.right,temp.left,tmptail.right,temp=temp.left,None,temp.right,tmptail
else:
temp=temp.right
return temp
``````

Non recursive one:

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

The code is based on the same algorithm from @zjulyx 's post.

When executed, the recursive one is 2x faster than its opposite. Any comments would be appreciated!

• In your recursive version, checking temp in the while loop is redundant and cause a lot of confusion. Actually, we need to ensure tmpTail (and hence temp since temp if the return value) can never be none in order for tmpTail.right = xxx works, so no need to check that in the while loop.

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