LeetCode 116. Populating Next Right Pointers in Each Node [Algorithm + Code Explained ]

One of the most frequently asked coding interview questions on Dynamic Programing on Tree in companies like Google, Facebook, Amazon, LinkedIn, Microsoft, Uber, Apple, Adobe etc.

LeetCode : Populating Next Right Pointers in Each Node

Question : You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

[shadowwolf]

can you explan why curr.next = q.peek(); LINE NUMBER - 39 ?

[shubhamsharma-sflx]

Please Make Populating Next pointers 2. Make harder tree problems

[anshumansolanki]

But the question says to solve it in constant extra space, using a queue violates that.

[jayatitiwari]

Hi All,

Using constant extra space, is another solution that I intend to post for LC 117 which is the part 2 of this question.

[code]

That's really nice. This kind of problems on trees that are tricky is really helpful

[gawarivivek]

Wow!! Understood the solution and code as well. Loved the approach!
It would be better if you dry run for a couple a few iterations. Also thanks for explaining the approach earlier, it makes more sense while seeing the code and making a dry run myself.
Great job indeed!!

[javi]

Hi Jayati, I found your explaination great. Keep posting interview preparation videos.

[cleadsouza]

You may only use constant extra space.

[paragroy]

Nice explanation madam but please add constant space solution would also be really helpful

[javacoder]

Thanks for the explanation! by the way how are you returning root when we are not doing anything to the root?

[akashparit]

mam can you tell in which case the "return root" after the while loop will get executed

[firecracker-ih]

i must say the approach is good but explanation is pathetic