Given a binary tree, connect the nodes that are at the same level. Given an addition nextRight pointer for the same. Initially, all the next right pointers point to garbage values, set these pointers to the point next right for each node.
Examples:
Input:
Output:
Explanation: The above tree represents the nextRight pointer connected the nodes that are at the same level.
Try it on GfG Practice
Table of Content
Using Level Order Traversal - O(n) Time and O(n) Space
The idea is to use line by line level order traversal, we mainly count nodes at next level using queue size. As nodes are processed, each node's nextRight pointer is set to the next node in the queue.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node *nextRight;
Node(int key) {
data = key;
left = nullptr;
right = nullptr;
nextRight = nullptr;
}
};
// Connect nodes using node count (level size)
Node* connect(Node *root) {
if (!root) return root;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int nodeCount = q.size();
for (int i = 0; i < nodeCount; i++) {
Node* node = q.front();
q.pop();
// Set nextRight
if (i == nodeCount - 1)
node->nextRight = nullptr;
else
node->nextRight = q.front();
// Push children
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return root;
}
int main() {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
Node *root = new Node(10);
root->left = new Node(8);
root->right = new Node(2);
root->left->left = new Node(3);
root->right->left = new Node(4);
connect(root);
cout << "Next Right of 8 is " << root->left->nextRight->data << endl;
cout << "Next Right of 3 is " << root->left->left->nextRight->data << endl;
return 0;
}
import java.util.*;
class GFG {
static class Node {
int data;
Node left, right, nextRight;
Node(int key) {
data = key;
left = right = nextRight = null;
}
}
// Connect nodes using node count (level size)
static Node connect(Node root) {
if (root == null) return root;
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int nodeCount = q.size();
for (int i = 0; i < nodeCount; i++) {
Node node = q.poll();
// Set nextRight
if (i == nodeCount - 1)
node.nextRight = null;
else
node.nextRight = q.peek();
// Push children
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
}
return root;
}
public static void main(String[] args) {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
Node root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.right.left = new Node(4);
connect(root);
System.out.println("Next Right of 8 is " + root.left.nextRight.data);
System.out.println("Next Right of 3 is " + root.left.left.nextRight.data);
}
}
from collections import deque
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
self.nextRight = None
# Connect nodes using node count (level size)
def connect(root):
if not root:
return root
q = deque([root])
while q:
nodeCount = len(q)
for i in range(nodeCount):
node = q.popleft()
# Set nextRight
if i == nodeCount - 1:
node.nextRight = None
else:
node.nextRight = q[0]
# Push children
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
# Constructed binary tree
# 10
# / \
# 8 2
# / /
# 3 4
if __name__ == "__main__":
root = Node(10)
root.left = Node(8)
root.right = Node(2)
root.left.left = Node(3)
root.right.left = Node(4)
connect(root)
print("Next Right of 8 is", root.left.nextRight.data)
print("Next Right of 3 is", root.left.left.nextRight.data)
using System;
using System.Collections.Generic;
class GFG {
public class Node {
public int data;
public Node left, right, nextRight;
public Node(int key) {
data = key;
left = right = nextRight = null;
}
}
// Connect nodes using node count (level size)
public static Node connect(Node root) {
if (root == null) return root;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0) {
int nodeCount = q.Count;
for (int i = 0; i < nodeCount; i++) {
Node node = q.Dequeue();
// Set nextRight
if (i == nodeCount - 1)
node.nextRight = null;
else
node.nextRight = q.Peek();
// Push children
if (node.left != null) q.Enqueue(node.left);
if (node.right != null) q.Enqueue(node.right);
}
}
return root;
}
public static void Main() {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
Node root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.right.left = new Node(4);
connect(root);
Console.WriteLine("Next Right of 8 is " + root.left.nextRight.data);
Console.WriteLine("Next Right of 3 is " + root.left.left.nextRight.data);
}
}
class Node {
constructor(key) {
this.data = key;
this.left = null;
this.right = null;
this.nextRight = null;
}
}
// Connect nodes using node count (level size)
function connect(root) {
if (!root) return root;
let q = [root];
while (q.length > 0) {
let nodeCount = q.length;
for (let i = 0; i < nodeCount; i++) {
let node = q.shift();
// Set nextRight
if (i === nodeCount - 1)
node.nextRight = null;
else
node.nextRight = q[0];
// Push children
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return root;
}
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
// Driver Code
let root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.right.left = new Node(4);
connect(root);
console.log("Next Right of 8 is " + root.left.nextRight.data);
console.log("Next Right of 3 is " + root.left.left.nextRight.data);
Output
Next Right of 8 is 2 Next Right of 3 is 4
[Expected Approach] Using Already Set Next Rights - O(n) Time and O(1) Space
- We traverse the tree level by level using the already established nextRight pointers.
- For each level, we iterate through all nodes using a loop and set nextRight of the next level.
- To set next right of children of a node, for left child, we first check for the right child. And then traverse to nextRight of the current node unilt we find a node that has at least one children.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right, *nextRight;
Node(int val) {
data = val;
left = right = nextRight = nullptr;
}
};
// Return the first node on the right
// side of q and at the next level
Node *getNextRight(Node *p) {
Node *temp = p->nextRight;
// Keep moving to next sibling until
// you find a sibling that has at least
// one children
while (temp != nullptr) {
if (temp->left != nullptr)
return temp->left;
if (temp->right != nullptr)
return temp->right;
temp = temp->nextRight;
}
return nullptr;
}
// Function to connect nodes at the same level
Node* connect(Node *root) {
Node *temp;
if (!root)
return nullptr ;
root->nextRight = nullptr;
while (root != nullptr) {
Node *q = root;
// Traverse all nodes at the current level
while (q != nullptr) {
if (q->left) {
if (q->right)
q->left->nextRight = q->right;
else
q->left->nextRight = getNextRight(q);
}
if (q->right)
q->right->nextRight = getNextRight(q);
q = q->nextRight;
}
// Move to the next level starting with the leftmost node
if (root->left)
root = root->left;
else if (root->right)
root = root->right;
else
root = getNextRight(root);
}
return root;
}
int main() {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
Node *root = new Node(10);
root->left = new Node(8);
root->right = new Node(2);
root->left->left = new Node(3);
root->right->left = new Node(4);
connect(root);
cout << "Next Right of 8 is " << root->left->nextRight->data << endl;
cout << "Next Right of 3 is " << root->left->left->nextRight->data << endl;
return 0;
}
import java.util.*;
class Node {
public int data;
public Node left, right, nextRight;
public Node(int val) {
data = val;
left = right = nextRight = null;
}
}
public class Main {
// Return the first node on the right
// side of q and at the next level
static Node getNextRight(Node p) {
Node temp = p.nextRight;
// Keep moving to next sibling until
// you find a sibling that has at least
// one children
while (temp!= null) {
if (temp.left!= null)
return temp.left;
if (temp.right!= null)
return temp.right;
temp = temp.nextRight;
}
return null;
}
// Function to connect nodes at the same level
static Node connect(Node root) {
Node temp;
if (root == null)
return null;
root.nextRight = null;
while (root!= null) {
Node q = root;
// Traverse all nodes at the current level
while (q!= null) {
if (q.left!= null) {
if (q.right!= null)
q.left.nextRight = q.right;
else
q.left.nextRight = getNextRight(q);
}
if (q.right!= null)
q.right.nextRight = getNextRight(q);
q = q.nextRight;
}
// Move to the next level starting with the leftmost node
if (root.left!= null)
root = root.left;
else if (root.right!= null)
root = root.right;
else
root = getNextRight(root);
}
return root;
}
public static void main(String[] args) {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
Node root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.right.left = new Node(4);
connect(root);
System.out.println("Next Right of 8 is " + root.left.nextRight.data);
System.out.println("Next Right of 3 is " + root.left.left.nextRight.data);
}
}
class Node:
def __init__(self, val):
self.data = val
self.left = self.right = self.nextRight = None
# Return the first node on the right
# side of q and at the next level
def get_next_right(p):
temp = p.nextRight
while temp is not None:
if temp.left is not None:
return temp.left
if temp.right is not None:
return temp.right
temp = temp.nextRight
return None
# Function to connect nodes at the same level
def connect(root):
if root is None:
return None
root.nextRight = None
while root is not None:
q = root
while q is not None:
if q.left is not None:
if q.right is not None:
q.left.nextRight = q.right
else:
q.left.nextRight = get_next_right(q)
if q.right is not None:
q.right.nextRight = get_next_right(q)
q = q.nextRight
if root.left is not None:
root = root.left
elif root.right is not None:
root = root.right
else:
root = get_next_right(root)
return root
if __name__ == '__main__':
# Constructed binary tree
# 10
# / \
# 8 2
# / /
# 3 4
root = Node(10)
root.left = Node(8)
root.right = Node(2)
root.left.left = Node(3)
root.right.left = Node(4)
connect(root)
print(f'Next Right of 8 is {root.left.nextRight.data}')
print(f'Next Right of 3 is {root.left.left.nextRight.data}')
using System;
public class Node {
public int data;
public Node left, right, nextRight;
public Node(int val) {
data = val;
left = right = nextRight = null;
}
}
public class Program {
// Return the first node on the right
// side of q and at the next level
static Node GetNextRight(Node p) {
Node temp = p.nextRight;
while (temp!= null) {
if (temp.left!= null)
return temp.left;
if (temp.right!= null)
return temp.right;
temp = temp.nextRight;
}
return null;
}
// Function to connect nodes at the same level
static Node Connect(Node root) {
if (root == null)
return null;
root.nextRight = null;
while (root!= null) {
Node q = root;
while (q!= null) {
if (q.left!= null) {
if (q.right!= null)
q.left.nextRight = q.right;
else
q.left.nextRight = GetNextRight(q);
}
if (q.right!= null)
q.right.nextRight = GetNextRight(q);
q = q.nextRight;
}
if (root.left!= null)
root = root.left;
else if (root.right!= null)
root = root.right;
else
root = GetNextRight(root);
}
return root;
}
public static void Main() {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
Node root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.right.left = new Node(4);
Connect(root);
Console.WriteLine("Next Right of 8 is " + root.left.nextRight.data);
Console.WriteLine("Next Right of 3 is " + root.left.left.nextRight.data);
}
}
class Node {
constructor(val) {
this.data = val;
this.left = this.right = this.nextRight = null;
}
}
// Return the first node on the right
// side of q and at the next level
function getNextRight(p) {
let temp = p.nextRight;
while (temp!== null) {
if (temp.left!== null)
return temp.left;
if (temp.right!== null)
return temp.right;
temp = temp.nextRight;
}
return null;
}
// Function to connect nodes at the same level
function connect(root) {
if (root === null)
return null;
root.nextRight = null;
while (root!== null) {
let q = root;
while (q!== null) {
if (q.left!== null) {
if (q.right!== null)
q.left.nextRight = q.right;
else
q.left.nextRight = getNextRight(q);
}
if (q.right!== null)
q.right.nextRight = getNextRight(q);
q = q.nextRight;
}
if (root.left!== null)
root = root.left;
else if (root.right!== null)
root = root.right;
else
root = getNextRight(root);
}
return root;
}
// Main function to test the connect function
function main() {
// Constructed binary tree
// 10
// / \
// 8 2
// / /
// 3 4
let root = new Node(10);
root.left = new Node(8);
root.right = new Node(2);
root.left.left = new Node(3);
root.right.left = new Node(4);
connect(root);
console.log(`Next Right of 8 is ${root.left.nextRight.data}`);
console.log(`Next Right of 3 is ${root.left.left.nextRight.data}`);
}
main();
Output
Next Right of 8 is 2 Next Right of 3 is 4