You have been given a complete binary tree of ‘N’ nodes. The nodes are numbered 1 to ‘N’.
You need to find the ‘next’ node that is immediately right in the level order form for each node in the given tree.
Note :
1. A complete binary tree is a binary tree in which nodes at all levels except the last level have two children and nodes at the last level have 0 children.
2. Node ‘U’ is said to be the next node of ‘V’ if and only if ‘U’ is just next to ‘V’ in tree representation.
3. Particularly root node and rightmost nodes have ‘next’ node equal to ‘Null’
4. Each node of the binary tree has three-pointers, ‘left’, ‘right’, and ‘next’. Here ‘left’ and ‘right’ are the children of node and ‘next’ is one extra pointer that we need to update.
For Example :
The‘next’ node for ‘1’ is ‘Null’, ‘2’ has ‘next’ node ‘6’, ‘5’ has ‘next’ node ‘3’, For the rest of the nodes check below.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example, the input for the tree is depicted in the below image.
1
2 3
4 5 6 7
-1 -1 -1 -1 -1 -1 -1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = 5
Left child of 3 =6
Right child of 3 = 7
Level 4 :
All children are ‘Null’
The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1
Output Format :
For each test case, print the tree’s level order traversal after updating ‘next’ node for each node where ‘-1’ denoting the null node.
The output of each test case will be printed in a separate line.
Note :
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
0 <= N <= 3000
1 <= data <= N
Where ‘data’ is the value of the node of the binary tree.
The given tree is always a Complete binary tree.
Time Limit: 1sec
CodingNinjas
author
2y
BFS approach
The idea here is to Perform BFS while maintaining all nodes of the same level together, which can be done by storing nodes of the same level in a queue data structure, then for a particular level, we start popping nodes one by one and set the ‘next’ pointer of the previously popped node to the current node.
Example :
Perform BFS and maintain a queue for all nodes at the current level.
Now, move to the next level and insert all nodes in the level to queue.
Similarly, for the next level.
Algorithm:
Declare a queue to store the nodes that are visited but not explored.
Push root node in the queue.
Explore Nodes until the queue is not empty.
The queue contains all nodes in the same level.
Declare a variable say ‘count’ equal to the current size of the queue.
Declare a Variable ‘prev’ to store the previously popped node.
Run a loop up to ‘count’ i.e. for all nodes from the current level.
Pop the node from the queue and store it in a variable say ‘currNode’.
If ‘currNode’ is not a left-most node. Set ‘prev->next’ = current popped node.
‘prev’ = ‘currNode’
Push the child of ‘currNode’ in the queue.
Finally, return the tree.
Space Complexity: O(n)Explanation:
O(N), where ‘N’ is the total number of nodes in the given binary tree.
We are storing nodes in the queue to perform BFS. In the worst case, the queue will store all the nodes in the last level of the binary tree which will be at least ‘N / 2’ in the count.
Hence, the overall space complexity will be O(N).
Time Complexity: O(n)Explanation:
O(N), where ‘N’ is the total number of nodes in the given binary tree.
We will visit each node exactly once while performing the BFS that takes O(N) time.
Hence, the overall time complexity will be O(N).
C++ (g++ 5.4)
/* Time Complexity: O(N) Space Complexity: O(N)
Where N is the total number of Nodes in the binary tree. */
void connectNext(TreeNode *root) { // If root is NULL then we don't need to modify any next pointer. if (root == NULL) { return; }
// Declare a queue data structure to store nodes during bfs queue *> q; q.push(root);
while (q.empty() == false) { // Declare a variable to store previously popped nodes TreeNode *prevNode;
// Declare a variable 'n' to store count of nodes at current level. int n = q.size();
for (int i = 0; i < n; i++) { TreeNode *currNode = q.front(); q.pop();
// Skip first popped node (left-most node) if (i > 0) { // Set next pointer of prevNode to currNode. prevNode -> next = currNode; }
// Push left child into queue if (currNode -> left != NULL) { q.push(currNode -> left); }
// Push right child into queue if (currNode -> right != NULL) { q.push(currNode -> right); }
prevNode = currNode; } } }
Java (SE 1.8)
/*
Time Complexity: O(N)
Space Complexity: O(N)
Where N is the total number of Nodes in the binary tree.
*/
public class Solution
{
public static void connectNext(TreeNode root)
{
// If root is NULL then we don't need to modify any next pointer.
if (root == null)
{
return;
}
// Declare a queue data structure to store nodes during bfs
Queue> q = new LinkedList<>();
q.add(root);
while (q.isEmpty() == false)
{
// Declare a variable to store previously popped nodes
TreeNode prevNode = root;
// Declare a variable 'n' to store count of nodes at current level.
int n = q.size();
for (int i = 0; i < n; i++)
{
TreeNode currNode = q.peek();
q.poll();
// Skip first popped node (left-most node)
if (i > 0)
{
// Set next pointer of prevNode to currNode.
prevNode.next = currNode;
}
// Push left child into queue
if (currNode.left != null)
{
q.add(currNode.left);
}
// Push right child into queue
if (currNode.right != null)
{
q.add(currNode.right);
}
prevNode = currNode;
}
}
}
}
Python (3.5)
'''
Time Complexity : O(N)
Space Complexity: O(N)
Where N is the total number of Nodes in the binary tree.
'''
from collections import deque
def connectNext(root):
# If root is None then we don't need to modify any next pointer.
if (root == None):
return
# Declare a queue data structure to store nodes during bfs
q = deque()
q.append(root)
while q :
# Declare a variable to store previously popped nodes
prevNode = root
# Declare a variable 'n' to store count of nodes at current level.
n = len(q)
for i in range(n):
currNode = q.popleft()
# Skip first popped node (left-most node)
if (i > 0):
# Set next pointer of prevNode to currNode.
prevNode.next = currNode
# Push left child into queue
if (currNode.left != None):
q.append(currNode.left)
# Push right child into queue
if (currNode.right != None):
q.append(currNode.right)
prevNode = currNode
CodingNinjas
author
2y
Using 'next' Pointer Of Parent Node
We know that the tree is complete i.e, all nodes have two children. So, we can use the parent node to populate the ‘next’ pointer of both children. The idea is to se...read more
