# A Python Solution with O(1) space complexity and simply explain

• An easy understood version with O(n) space complexity.

``````class Solution(object):
def connect(self, root):
"""
:rtype: nothing
"""
if root is None:
return
stack = [root]
while len(stack) is not 0:
length = len(stack)
for i in xrange(0, length-1):
stack[i].next = stack[i+1]
nextStack = []
for node in stack:
if node.left != None:
nextStack.append(node.left)
if node.right != None:
nextStack.append(node.right)
stack = nextStack
return
``````

The space complexity of following code is O(1), which connects node level by level.
Actually the two code connecting nodes in same order, and the following code traversing the nodes on the next level by next pointer while the code above use stack to save the nodes in next level to traversal.

``````class Solution(object):
def connect(self, root):
"""
:rtype: nothing
"""
if root is None:
return
while root is not None:
while root != None and root.left is None and root.right is None:
root = root.next
if root == None:    return
if root.left != None:
root.left.next = root.right
pre = root.left
if root.right != None:
pre = root.right
nextNode = root.next
while nextNode != None:
if nextNode.left != None:
nextNode.left.next = nextNode.right
pre.next = nextNode.left
pre = nextNode.left
if nextNode.right != None:
pre = nextNode.right
elif nextNode.right != None:
pre.next = nextNode.right
pre = nextNode.right
nextNode = nextNode.next
if root.left != None:
root = root.left
else:
root = root.right
return``````

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