# My accepted non recursive solution in python based on level order traverse

• ``````class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
if not root:
return None
tmpLeft,queue=root,[]
if tmpLeft.left and tmpLeft.right:
queue.append(tmpLeft.left)
queue.append(tmpLeft.right)
k,label,range=1,0,1
# use a queue to perform level order traverse
while queue:
tmpRight=queue.pop(0)
if tmpRight.left and tmpRight.right:
queue.append(tmpRight.left)
queue.append(tmpRight.right)
if k<label+range: # the combination of k label and range to determine whether the current note is located at the right edge
tmpLeft.next=tmpRight
else:
tmpLeft.next=None
label+=range
# the number of nodes is doubled compared the number of nodes of previous level
range+=range
tmpLeft=tmpRight
k+=1
tmpLeft.next=None
``````

The code is based on the level order traverse. Any comments would be appreciated!

• The question asked for constant extra space. I'm afraid as long as you use a queue, the space complexity is not constant anymore.

• Would you mind sharing a solution that uses constant space. Recursion uses a stack and I wonder how this can be otherwise resolved. I am afraid if the question is wrongly quoted.

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