Given a Binary Tree rooted at node 1, the task is to print the elements in the following defined order.
- First, print all elements of the last level in an alternate way such as first you print leftmost element and then rightmost element & continue in this until all elements are traversed of last level.
- Now do the same for the rest of the levels.
Examples:
Input: 1 / \ 2 3 / \ / 4 5 6 Output: 4 6 5 2 3 1 Explanation: First print all elements of the last level which will be printed as follows: 4 6 5 Now tree becomes 1 / \ 2 3 Now print elements as 2 3 Now the tree becomes: 1 Input: 1 / \ 2 3 Output: 2 3 1
Approach:
- Make a bfs call and store all the nodes present at level i into a vector array.
- Also keep track of maximum level reached in a bfs call.
- Now print the desired pattern starting from max level to 0
Below is the implementation of the above approach:
C++
// C++ implementation // for the above approach #include <bits/stdc++.h> using namespace std; const int sz = 1e5; int maxLevel = 0; // Adjacency list // representation of the tree vector< int > tree[sz + 1]; // Boolean array to mark all the // vertices which are visited bool vis[sz + 1]; // Integer array to store // the level of each node int level[sz + 1]; // Array of vector where ith index // stores all the nodes at level i vector< int > nodes[sz + 1]; // Utility function to create an // edge between two vertices void addEdge( int a, int b) { // Add a to b's list tree[a].push_back(b); // Add b to a's list tree[b].push_back(a); } // Modified Breadth-First Function void bfs( int node) { // Create a queue of {child, parent} queue<pair< int , int > > qu; // Push root node in the front of // the queue and mark as visited qu.push({ node, 0 }); nodes[0].push_back(node); vis[node] = true ; level[1] = 0; while (!qu.empty()) { pair< int , int > p = qu.front(); // Dequeue a vertex from queue qu.pop(); vis[p.first] = true ; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue it for ( int child : tree[p.first]) { if (!vis[child]) { qu.push({ child, p.first }); level[child] = level[p.first] + 1; maxLevel = max(maxLevel, level[child]); nodes[level[child]].push_back(child); } } } } // Function to display // the pattern void display() { for ( int i = maxLevel; i >= 0; i--) { int len = nodes[i].size(); // Printing all nodes // at given level for ( int j = 0; j < len / 2; j++) { cout << nodes[i][j] << " " << nodes[i][len - 1 - j] << " " ; } // If count of nodes // at level i is odd // print remaining node if (len % 2 == 1) { cout << nodes[i][len / 2] << " " ; } } } // Driver code int main() { // Number of vertices int n = 6; addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); // Calling modified bfs function bfs(1); display(); return 0; } |
Java
// Java implementation // for the above approach import java.util.*; @SuppressWarnings ( "unchecked" ) class GFG{ static int sz = 100000 ; static int maxLevel = 0 ; // Adjacency list // representation of the tree static ArrayList []tree = new ArrayList[sz + 1 ]; // boolean array to mark all the // vertices which are visited static boolean []vis = new boolean [sz + 1 ]; // Integer array to store // the level of each node static int []level = new int [sz + 1 ]; // Array of vector where ith index // stores all the nodes at level i static ArrayList []nodes = new ArrayList[sz + 1 ]; // Utility function to create an // edge between two vertices static void addEdge( int a, int b) { // Add a to b's list tree[a].add(b); // Add b to a's list tree[b].add(a); } static class Pair { int Key, Value; Pair( int Key, int Value) { this .Key = Key; this .Value = Value; } } // Modified Breadth-Key Function static void bfs( int node) { // Create a queue of {child, parent} Queue<Pair> qu = new LinkedList<>(); // Push root node in the front of // the queue and mark as visited qu.add( new Pair(node, 0 )); nodes[ 0 ].add(node); vis[node] = true ; level[ 1 ] = 0 ; while (qu.size() != 0 ) { Pair p = qu.poll(); // Dequeue a vertex from queue vis[p.Key] = true ; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then put it for ( int child : (ArrayList<Integer>)tree[p.Key]) { if (!vis[child]) { qu.add( new Pair(child, p.Key)); level[child] = level[p.Key] + 1 ; maxLevel = Math.max(maxLevel, level[child]); nodes[level[child]].add(child); } } } } // Function to display // the pattern static void display() { for ( int i = maxLevel; i >= 0 ; i--) { int len = nodes[i].size(); // Printing all nodes // at given level for ( int j = 0 ; j < len / 2 ; j++) { System.out.print(( int )nodes[i].get(j) + " " + ( int )nodes[i].get(len - 1 - j) + " " ); } // If count of nodes // at level i is odd // print remaining node if (len % 2 == 1 ) { System.out.print( ( int )nodes[i].get(len / 2 ) + " " ); } } } // Driver code public static void main(String[] args) { for ( int i = 0 ; i < sz + 1 ; i++) { tree[i] = new ArrayList(); nodes[i] = new ArrayList(); vis[i] = false ; level[i] = 0 ; } addEdge( 1 , 2 ); addEdge( 1 , 3 ); addEdge( 2 , 4 ); addEdge( 2 , 5 ); addEdge( 3 , 6 ); // Calling modified bfs function bfs( 1 ); display(); } } // This code is contributed by pratham76 |
Python3
# Python3 implementation # for the above approach from collections import deque sz = 10 * * 5 maxLevel = 0 # Adjacency list # representation of the tree tree = [[] for i in range (sz + 1 )] # Boolean array to mark all the # vertices which are visited vis = [ False ] * (sz + 1 ) # Integer array to store # the level of each node level = [ 0 ] * (sz + 1 ) # Array of vector where ith index # stores all the nodes at level i nodes = [[] for i in range (sz + 1 )] # Utility function to create an # edge between two vertices def addEdge(a, b): global tree # Add a to b's list tree[a].append(b) # Add b to a's list tree[b].append(a) # Modified Breadth-First Function def bfs(node): global maxLevel # Create a queue of {child, parent} qu = deque() # Push root node in the front of # the queue and mark as visited qu.append([node, 0 ]) nodes[ 0 ].append(node) vis[node] = True level[ 1 ] = 0 while ( len (qu) > 0 ): p = qu.popleft() # Dequeue a vertex from queue # qu.pop() vis[p[ 0 ]] = True # Get all adjacent vertices of the dequeued # vertex s. If any adjacent has not # been visited then enqueue it for child in tree[p[ 0 ]]: if ( not vis[child]): qu.append([child, p[ 0 ]]) level[child] = level[p[ 0 ]] + 1 maxLevel = max (maxLevel, level[child]) nodes[level[child]].append(child) # Function to display # the pattern def display(): for i in range (maxLevel, - 1 , - 1 ): lenn = len (nodes[i]) # Printing all nodes # at given level for j in range (lenn / / 2 ): print (nodes[i][j], nodes[i][lenn - 1 - j], end = " " ) # If count of nodes # at level i is odd # print remaining node if (lenn % 2 = = 1 ): print (nodes[i][lenn / / 2 ], end = " " ) # Driver code if __name__ = = '__main__' : # Number of vertices n = 6 addEdge( 1 , 2 ) addEdge( 1 , 3 ) addEdge( 2 , 4 ) addEdge( 2 , 5 ) addEdge( 3 , 6 ) # Calling modified bfs function bfs( 1 ) display() # This code is contributed by mohit kumar 29 |
C#
// C# implementation // for the above approach using System; using System.Collections.Generic; using System.Collections; class GFG{ static int sz = 100000; static int maxLevel = 0; // Adjacency list // representation of the tree static ArrayList []tree = new ArrayList[sz + 1]; // Boolean array to mark all the // vertices which are visited static bool []vis = new bool [sz + 1]; // Integer array to store // the level of each node static int []level = new int [sz + 1]; // Array of vector where ith index // stores all the nodes at level i static ArrayList []nodes = new ArrayList[sz + 1]; // Utility function to create an // edge between two vertices static void addEdge( int a, int b) { // Add a to b's list tree[a].Add(b); // Add b to a's list tree[b].Add(a); } // Modified Breadth-First Function static void bfs( int node) { // Create a queue of {child, parent} Queue qu = new Queue(); // Push root node in the front of // the queue and mark as visited qu.Enqueue( new KeyValuePair< int , int >(node, 0)); nodes[0].Add(node); vis[node] = true ; level[1] = 0; while (qu.Count != 0) { KeyValuePair< int , int > p = (KeyValuePair< int , int >)qu.Peek(); // Dequeue a vertex from queue qu.Dequeue(); vis[p.Key] = true ; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue it foreach ( int child in tree[p.Key]) { if (!vis[child]) { qu.Enqueue( new KeyValuePair< int , int >( child, p.Key)); level[child] = level[p.Key] + 1; maxLevel = Math.Max(maxLevel, level[child]); nodes[level[child]].Add(child); } } } } // Function to display // the pattern static void display() { for ( int i = maxLevel; i >= 0; i--) { int len = nodes[i].Count; // Printing all nodes // at given level for ( int j = 0; j < len / 2; j++) { Console.Write(( int )nodes[i][j] + " " + ( int )nodes[i][len - 1 - j] + " " ); } // If count of nodes // at level i is odd // print remaining node if (len % 2 == 1) { Console.Write(( int )nodes[i][len / 2] + " " ); } } } // Driver code public static void Main( string [] args) { for ( int i = 0; i < sz + 1; i++) { tree[i] = new ArrayList(); nodes[i] = new ArrayList(); vis[i] = false ; level[i] = 0; } addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); // Calling modified bfs function bfs(1); display(); } } // This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript implementation // for the above approach let sz = 100000; let maxLevel = 0; // Adjacency list // representation of the tree let tree = new Array(sz + 1); // boolean array to mark all the // vertices which are visited let vis = new Array(sz + 1); // Integer array to store // the level of each node let level = new Array(sz + 1); // Array of vector where ith index // stores all the nodes at level i let nodes = new Array(sz + 1); // Utility function to create an // edge between two vertices function addEdge(a,b) { // Add a to b's list tree[a].push(b); // Add b to a's list tree[b].push(a); } // Modified Breadth-Key Function function bfs(node) { let qu=[]; // Push root node in the front of // the queue and mark as visited qu.push([node, 0]); nodes[0].push(node); vis[node] = true ; level[1] = 0; while (qu.length != 0) { let p = qu.shift(); // Dequeue a vertex from queue vis[p[0]] = true ; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then put it for (let child=0;child<tree[p[0]].length;child++) { if (!vis[tree[p[0]][child]]) { qu.push([tree[p[0]][child], p[0]]); level[tree[p[0]][child]] = level[p[0]] + 1; maxLevel = Math.max(maxLevel, level[tree[p[0]][child]]); nodes[level[tree[p[0]][child]]]. push(tree[p[0]][child]); } } } } // Function to display // the pattern function display() { for (let i = maxLevel; i >= 0; i--) { let len = nodes[i].length; // Printing all nodes // at given level for (let j = 0; j < Math.floor(len / 2); j++) { document.write(nodes[i][j] + " " + nodes[i][len - 1 - j] + " " ); } // If count of nodes // at level i is odd // print remaining node if (len % 2 == 1) { document.write( nodes[i][(Math.floor(len / 2))] + " " ); } } } // Driver code for (let i = 0; i < sz + 1; i++) { tree[i] = []; nodes[i] = []; vis[i] = false ; level[i] = 0; } addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); // Calling modified bfs function bfs(1); display(); // This code is contributed by patel2127 </script> |
4 6 5 2 3 1
Time Complexity: O(V + E), where V is total number of vertices and E is total number of edges.
Auxiliary Space: O(V).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!