# AC Python O(1) space solution 12 lines and easy to understand

• The algorithm is a BFS or level order traversal. We go through the tree level by level. node is the pointer in the parent level, tail is the tail pointer in the child level.
The parent level can be view as a singly linked list or queue, which we can traversal easily with a pointer.
Connect the tail with every one of the possible nodes in child level, update it only if the connected node is not nil.
Do this one level by one level. The whole thing is quite straightforward.

Python

``````def connect(self, node):
while node:
tail.next = node.left
if tail.next:
tail = tail.next
tail.next = node.right
if tail.next:
tail = tail.next
node = node.next
if not node:
tail = dummy
node = dummy.next

# 61 / 61 test cases passed.
# Status: Accepted
# Runtime: 100 ms
# 95.26%``````

• @dietpepsi Elegant! Great use of dummy pointer. Thanks for the solution!

• Hi, thank you for sharing the code. I really have difficulty in understanding how the dummy works: it seems to me that dummy is a floating node all the time, and at the end of every level, node will become Null since it is assigned to dummy.next. Therefore, node will not pass the while condition for every level, actually it should get stuck for the 1st round (root node). I'm really struggling where I got wrong. Could you help to point out? Thank you so much!

• For the benefit of others, here is more intuitive code with more clear names to clarify their meaning and purpose. Whole credit is to @dietpepsi whose this post actually inspired me to think of linked list as a queue

``````class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
if not root:
return

# enqueue root
front = root
front.next = rear

while front is not rear:
# dequeue from front
node  = front
front = front.next
# if sentinel is dequeued
if node is sentinel:
# if rear has non sentinel items
# enqueue sentinel back
if rear is not sentinel:
rear.next = sentinel
rear = rear.next
continue

if node.next is sentinel: # full level is traversed
node.next = None

# enqueue left
if node.left:
rear.next = node.left
rear = rear.next
# enqueue right
if node.right:
rear.next = node.right
rear = rear.next``````

• @gaosuwoniu The first line where we make tail and dummy equal to same tree node that we newly created.

Afterwards in while loop, first line we make tail.next equal to node.left which is the left node (of the current node being traversed) in original tree. So if python assignment works the same as pointers in C, in this line essentially we are also setting dummy.next to node.left, because they are pointing towards same node.

tail.next = node.left

now in the last line of the function we are equating node = dummy.next which is pointing to node.left since we did not move it at all in the entire loop. That is how its going to the next level.

• ``````My python solution
def connect(self, root):
while root:
while root:
if root.left:
cur.next = root.left
cur = root.left
if root.right:
cur.next = root.right
cur = root.right
root = root.next
root = tmp.next``````

• This post is deleted!

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