Connect Nodes at same Level (Level Order Traversal)
Write a function to connect all the adjacent nodes at the same level in a binary tree.
Example:
Input Tree A / \ B C / \ \ D E F Output Tree A--->NULL / \ B-->C-->NULL / \ \ D-->E-->F-->NULL
We have already discussed O(n^2) time and O approach in Connect nodes at same level as morris traversal in worst case can be O(n) and calling it to set right pointer can result in O(n^2) time complexity.
In this post, We have discussed Level Order Traversal with NULL markers which are needed to mark levels in tree.
Implementation:
C++
// Connect nodes at same level using level order // traversal. #include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* left, *right, *nextRight; }; // Sets nextRight of all nodes of a tree void connect( struct Node* root) { queue<Node*> q; q.push(root); // null marker to represent end of current level q.push(NULL); // Do Level order of tree using NULL markers while (!q.empty()) { Node *p = q.front(); q.pop(); if (p != NULL) { // next element in queue represents next // node at current Level p->nextRight = q.front(); // push left and right children of current // node if (p->left) q.push(p->left); if (p->right) q.push(p->right); } // if queue is not empty, push NULL to mark // nodes at this level are visited else if (!q.empty()) q.push(NULL); } } /* UTILITY FUNCTIONS */ /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct Node* newnode( int data) { struct Node* node = ( struct Node*) malloc ( sizeof ( struct Node)); node->data = data; node->left = node->right = node->nextRight = NULL; return (node); } /* Driver program to test above functions*/ int main() { /* Constructed binary tree is 10 / \ 8 2 / \ 3 90 */ struct Node* root = newnode(10); root->left = newnode(8); root->right = newnode(2); root->left->left = newnode(3); root->right->right = newnode(90); // Populates nextRight pointer in all nodes connect(root); // Let us check the values of nextRight pointers printf ( "Following are populated nextRight pointers in \n" "the tree (-1 is printed if there is no nextRight) \n" ); printf ( "nextRight of %d is %d \n" , root->data, root->nextRight ? root->nextRight->data : -1); printf ( "nextRight of %d is %d \n" , root->left->data, root->left->nextRight ? root->left->nextRight->data : -1); printf ( "nextRight of %d is %d \n" , root->right->data, root->right->nextRight ? root->right->nextRight->data : -1); printf ( "nextRight of %d is %d \n" , root->left->left->data, root->left->left->nextRight ? root->left->left->nextRight->data : -1); printf ( "nextRight of %d is %d \n" , root->right->right->data, root->right->right->nextRight ? root->right->right->nextRight->data : -1); return 0; } |
Java
// Connect nodes at same level using level order // traversal. import java.util.LinkedList; import java.util.Queue; public class Connect_node_same_level { // Node class static class Node { int data; Node left, right, nextRight; Node( int data){ this .data = data; left = null ; right = null ; nextRight = null ; } }; // Sets nextRight of all nodes of a tree static void connect(Node root) { Queue<Node> q = new LinkedList<Node>(); q.add(root); // null marker to represent end of current level q.add( null ); // Do Level order of tree using NULL markers while (!q.isEmpty()) { Node p = q.peek(); q.remove(); if (p != null ) { // next element in queue represents next // node at current Level p.nextRight = q.peek(); // push left and right children of current // node if (p.left != null ) q.add(p.left); if (p.right != null ) q.add(p.right); } // if queue is not empty, push NULL to mark // nodes at this level are visited else if (!q.isEmpty()) q.add( null ); } } /* Driver program to test above functions*/ public static void main(String args[]) { /* Constructed binary tree is 10 / \ 8 2 / \ 3 90 */ Node root = new Node( 10 ); root.left = new Node( 8 ); root.right = new Node( 2 ); root.left.left = new Node( 3 ); root.right.right = new Node( 90 ); // Populates nextRight pointer in all nodes connect(root); // Let us check the values of nextRight pointers System.out.println( "Following are populated nextRight pointers in \n" + "the tree (-1 is printed if there is no nextRight)" ); System.out.println( "nextRight of " + root.data + " is " + ((root.nextRight != null ) ? root.nextRight.data : - 1 )); System.out.println( "nextRight of " + root.left.data+ " is " + ((root.left.nextRight != null ) ? root.left.nextRight.data : - 1 )); System.out.println( "nextRight of " + root.right.data+ " is " + ((root.right.nextRight != null ) ? root.right.nextRight.data : - 1 )); System.out.println( "nextRight of " + root.left.left.data+ " is " + ((root.left.left.nextRight != null ) ? root.left.left.nextRight.data : - 1 )); System.out.println( "nextRight of " + root.right.right.data+ " is " + ((root.right.right.nextRight != null ) ? root.right.right.nextRight.data : - 1 )); } } // This code is contributed by Sumit Ghosh |
Python3
#! /usr/bin/env python3 # connect nodes at same level using level order traversal import sys class Node: def __init__( self , data): self .data = data self .left = None self .right = None self .nextRight = None def __str__( self ): return '{}' . format ( self .data) def printLevelByLevel(root): # print level by level if root: node = root while node: print ( '{}' . format (node.data), end = ' ' ) node = node.nextRight print () if root.left: printLevelByLevel(root.left) else : printLevelByLevel(root.right) def inorder(root): if root: inorder(root.left) print (root.data, end = ' ' ) inorder(root.right) def connect(root): # set nextRight of all nodes of a tree queue = [] queue.append(root) # null marker to represent end of current level queue.append( None ) # do level order of tree using None markers while queue: p = queue.pop( 0 ) if p: # next element in queue represents # next node at current level p.nextRight = queue[ 0 ] # push left and right children of current node if p.left: queue.append(p.left) if p.right: queue.append(p.right) elif queue: queue.append( None ) def main(): """Driver program to test above functions. Constructed binary tree is 10 / \ 8 2 / \ 3 90 """ root = Node( 10 ) root.left = Node( 8 ) root.right = Node( 2 ) root.left.left = Node( 3 ) root.right.right = Node( 90 ) # Populates nextRight pointer in all nodes connect(root) # Let us check the values of nextRight pointers print ( "Following are populated nextRight pointers in \n" "the tree (-1 is printed if there is no nextRight) \n" ) if (root.nextRight ! = None ): print ( "nextRight of %d is %d \n" % (root.data,root.nextRight.data)) else : print ( "nextRight of %d is %d \n" % (root.data, - 1 )) if (root.left.nextRight ! = None ): print ( "nextRight of %d is %d \n" % (root.left.data,root.left.nextRight.data)) else : print ( "nextRight of %d is %d \n" % (root.left.data, - 1 )) if (root.right.nextRight ! = None ): print ( "nextRight of %d is %d \n" % (root.right.data,root.right.nextRight.data)) else : print ( "nextRight of %d is %d \n" % (root.right.data, - 1 )) if (root.left.left.nextRight ! = None ): print ( "nextRight of %d is %d \n" % (root.left.left.data,root.left.left.nextRight.data)) else : print ( "nextRight of %d is %d \n" % (root.left.left.data, - 1 )) if (root.right.right.nextRight ! = None ): print ( "nextRight of %d is %d \n" % (root.right.right.data,root.right.right.nextRight.data)) else : print ( "nextRight of %d is %d \n" % (root.right.right.data, - 1 )) print () if __name__ = = "__main__" : main() # This code is contributed by Ram Basnet |
C#
// Connect nodes at same level using level order // traversal. using System; using System.Collections.Generic; public class Connect_node_same_level { // Node class class Node { public int data; public Node left, right, nextRight; public Node( int data) { this .data = data; left = null ; right = null ; nextRight = null ; } }; // Sets nextRight of all nodes of a tree static void connect(Node root) { Queue<Node> q = new Queue<Node>(); q.Enqueue(root); // null marker to represent end of current level q.Enqueue( null ); // Do Level order of tree using NULL markers while (q.Count!=0) { Node p = q.Peek(); q.Dequeue(); if (p != null ) { // next element in queue represents next // node at current Level p.nextRight = q.Peek(); // push left and right children of current // node if (p.left != null ) q.Enqueue(p.left); if (p.right != null ) q.Enqueue(p.right); } // if queue is not empty, push NULL to mark // nodes at this level are visited else if (q.Count!=0) q.Enqueue( null ); } } /* Driver code*/ public static void Main() { /* Constructed binary tree is 10 / \ 8 2 / \ 3 90 */ Node root = new Node(10); root.left = new Node(8); root.right = new Node(2); root.left.left = new Node(3); root.right.right = new Node(90); // Populates nextRight pointer in all nodes connect(root); // Let us check the values of nextRight pointers Console.WriteLine( "Following are populated nextRight pointers in \n" + "the tree (-1 is printed if there is no nextRight)" ); Console.WriteLine( "nextRight of " + root.data + " is " + ((root.nextRight != null ) ? root.nextRight.data : -1)); Console.WriteLine( "nextRight of " + root.left.data+ " is " + ((root.left.nextRight != null ) ? root.left.nextRight.data : -1)); Console.WriteLine( "nextRight of " + root.right.data+ " is " + ((root.right.nextRight != null ) ? root.right.nextRight.data : -1)); Console.WriteLine( "nextRight of " + root.left.left.data+ " is " + ((root.left.left.nextRight != null ) ? root.left.left.nextRight.data : -1)); Console.WriteLine( "nextRight of " + root.right.right.data+ " is " + ((root.right.right.nextRight != null ) ? root.right.right.nextRight.data : -1)); } } /* This code is contributed by Rajput-Ji*/ |
Javascript
<script> // Connect nodes at same level using level order traversal. // A Binary Tree Node class Node { constructor(data, nextRight) { this .left = null ; this .right = null ; this .data = data; this .nextRight = nextRight; } } // Sets nextRight of all nodes of a tree function connect(root) { let q = []; q.push(root); // null marker to represent end of current level q.push( null ); // Do Level order of tree using NULL markers while (q.length > 0) { let p = q[0]; q.shift(); if (p != null ) { // next element in queue represents next // node at current Level p.nextRight = q[0]; // push left and right children of current // node if (p.left != null ) q.push(p.left); if (p.right != null ) q.push(p.right); } // if queue is not empty, push NULL to mark // nodes at this level are visited else if (q.length > 0) q.push( null ); } } /* Constructed binary tree is 10 / \ 8 2 / \ 3 90 */ let root = new Node(10); root.left = new Node(8); root.right = new Node(2); root.left.left = new Node(3); root.right.right = new Node(90); // Populates nextRight pointer in all nodes connect(root); // Let us check the values of nextRight pointers document.write( "Following are populated nextRight pointers in " + "</br>" + "the tree (-1 is printed if there is no nextRight)" + "</br>" ); document.write( "nextRight of " + root.data + " is " + ((root.nextRight != null ) ? root.nextRight.data : -1) + "</br>" ); document.write( "nextRight of " + root.left.data+ " is " + ((root.left.nextRight != null ) ? root.left.nextRight.data : -1) + "</br>" ); document.write( "nextRight of " + root.right.data+ " is " + ((root.right.nextRight != null ) ? root.right.nextRight.data : -1) + "</br>" ); document.write( "nextRight of " + root.left.left.data+ " is " + ((root.left.left.nextRight != null ) ? root.left.left.nextRight.data : -1) + "</br>" ); document.write( "nextRight of " + root.right.right.data+ " is " + ((root.right.right.nextRight != null ) ? root.right.right.nextRight.data : -1) + "</br>" ); // This code is contributed by divyesh072019. </script> |
Following are populated nextRight pointers in the tree (-1 is printed if there is no nextRight) nextRight of 10 is -1 nextRight of 8 is 2 nextRight of 2 is -1 nextRight of 3 is 90 nextRight of 90 is -1
Time complexity: O(n) where n is the number of nodes
Auxiliary Space: O(n) for queue
Alternate Implementation:
We can also follow the implementation discussed in Print level order traversal line by line | Set 1. We keep connecting nodes of same level by keeping track of previous visited node of same level.
Implementation : https://ide.w3wiki.net/gV1Oc2
Thanks to Akilan Sengottaiyan for suggesting this alternate implementation.