# O(1) space Python Solution with explanation

• ``````    current_node = root
need_to_assign = '<EMPTY_NODE>'
next_layer_start = '<EMPTY_NODE>'

while True:
# search for start of next layer
if next_layer_start == '<EMPTY_NODE>':
if current_node.left != None:
next_layer_start = current_node.left
elif current_node.right != None:
next_layer_start = current_node.right

# try to link the former node and update 'need_to_assign'
if need_to_assign == '<EMPTY_NODE>':
if current_node.right != None:
need_to_assign = current_node.right
elif current_node.left != None:
need_to_assign = current_node.left
else:
if current_node.left != None and current_node.right == None:
need_to_assign.next = current_node.left
need_to_assign = current_node.left
elif current_node.left == None and current_node.right != None:
need_to_assign.next = current_node.right
need_to_assign = current_node.right
elif current_node.left != None and current_node.right != None:
need_to_assign.next = current_node.left
need_to_assign = current_node.right

# try to link left child to right child
if current_node.left != None and current_node.right != None:
current_node.left.next = current_node.right

# go to next node on the same level or go to next level
if current_node.next != None:
current_node = current_node.next
else:
if next_layer_start == '<EMPTY_NODE>':
break
current_node = next_layer_start
need_to_assign = '<EMPTY_NODE>'
next_layer_start = '<EMPTY_NODE>'``````

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