Binary Tree - 75: Connect Nodes at same Level with 'next' pointer

Solution - 1:
- We do level order traversal & maintain a previous node
- At starting of every level, we set previous to null
- While traversing a npde, we point next of previous to current node

Time Complexity: O(n)
Space Complexity: O(n)

Solution - 2:
- We traverse the binary tree in pre-order manner
- We keep on adding the next pointer for a level

Time Complexity: O(n)
Space Complexity: O(1)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 200+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[shrad]

Instead use this code, its very simple :
static void connect(Node root)
{
Queue<Node> q = new LinkedList<Node>();
q.add(root);

// Do Level order of tree using NULL markers
while (!q.isEmpty()) {
int size = q.size();
while(size > 0){
Node p = q.poll();

if(size == 1){
p.nextRight = null;
}else{
p.nextRight = q.peek();
}
if (p.left != null)
q.add(p.left);
if (p.right != null)
q.add(p.right);
size--;
}
}
}

[rohitpawar]

Your content is awesome sir i regret that ye channel mujha pehla kyu nahi mila

[abhishekshankar]

i used a vector of nodes to maintain the level, then iterated over it and made next right of each node point to i+1 ... solution was still accepted

[vanditkhuranapvt]

Why we used the prev node for solving this question?

[NoOne-gswn]

In the else condition you wrote temp.right = getNextRIght(temp).
This is called when the temp.right==null and if you call this won't it change the structure of tree ?
Shouldn't it be temp.left.right = getNextRIght(temp)?

[divyagupta]

There is a mistake in your code in the else part it should be