@ashwath Can someone explain me this line "root = tempChild.next". I understand the notion is that after each level the tempChild points to the left most node in the next level. But I am not able to understand how tempChild pointer changes.
There is only 2 places where this tempChild is in code. tempChild was introduced in line 1. Never changed to anything. Even its next was null till the second last line. The how "root = tempChild.next " doesn't make root == null on this line?
when root == null, it means that this is the last node in this layer. Currently you can think dummyHead is a head of a LinkedList, dummyHead.next is the starting node of next layer.
So, when we come to the last node, we need to shift to next layer, that's why we need to have root = dummyHead.next.
we need to reset our helper pointer pre to dummyHead. And finally, cut off all the previous node because it does not belong to this layer.
My python solution
def connect(self, root):
cur = tmp = TreeLinkNode(0)
cur.next = root.left
cur = root.left
cur.next = root.right
cur = root.right
root = root.next
root = tmp.next
Actually, as mentioned in the comments above, it is possible to get the best of the two worlds in Java: allocate a sentinel, but only do it once and then reuse it. This makes the whole thing faster, makes life easier for the GC, and keeps the code as branch-free as possible.
Good answer, while the first BFS case can also be written as:
# BFS with queue
def connect(self, root):
if not root:
queue, nextLevel = [root],  # queue records the previous level
curr = queue.pop(0)
curr.next = queue
if not queue and nextLevel:
queue, nextLevel = nextLevel, queue
Could you please explain the space complexity to me?
I saw some posts talking about creating new node in each level causes O(1) space.
and there are log n levels, so the space complexity is O(log n)?
but I also find some people say algorithms like yours is space O(1)
Sure. firstNode is the dummy head of the next level, so firstNode.next will be the actual first node of next level. We use pre to record the previous node in next level and pre is initialized to firstNode.
Yes, I worked out the issue here. There are several border cases that I did not consider carefully.
How the tree look like in LeetCode, for this question, it has deliberate explanation under each question. I'm sure you can find the link.
I can give you the example here. For the input you mentioned, the tree should be
Explanation for 2nd solution: It's a BFS traversal inspired by aileengw. The curr pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move curr pointer at current level and populate the the next-link at its children level. (Here the gist is we can move curr to its next because this relationship was already populated in the previous round).