Given a Complete Binary Tree, the task is to print the elements in the following pattern. Let’s consider the tree to be:
The tree is traversed in the following way:
The output for the above tree is:
1 3 7 11 10 9 8 4 5 6 2
Approach: The idea is to use the modified breadth first search function to store all the nodes at every level in an array of vector. Along with it, the maximum level up to which the tree needs to be traversed is also stored in a variable. After this precomputation task, the following steps are followed to get the required answer:
- Create a vector tree[] where tree[i] will store all the nodes of the tree at the level i.
- Take an integer variable k which keeps the track of the level number that is being traversed and another integer variable path which keeps the track of the number of cycles that have been completed. A flag variable is also created to keep the track of the direction in which the tree is being traversed.
- Now, start printing the rightmost nodes at each level until the maximum level is reached.
- Since the maximum level is reached, the direction has to be changed. In the last level, print elements from rightmost to left. And the value of maxLevel variable has to be decremented.
- As the tree is being traversed from the lower level to the upper level, the rightmost elements are printed. Since in the next iteration, the maxlevel value has been changed, it makes sure that already visited nodes in the last level are not traversed again.
Below is the implementation of the above approach:
C++
// C++ program to print sideways // traversal of complete binary tree #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); } } } } // Utility Function to display the pattern void display() { // k represents the level no. // cycle represents how many // cycles has been completed int k = 0, path = 0; int condn = (maxLevel) / 2 + 1; bool flag = true ; // While there are nodes left to traverse while (condn--) { if (flag) { // Traversing whole level from // left to right int j = nodes[k].size() - 1; for (j = 0; j < nodes[k].size() - path; j++) cout << nodes[k][j] << " " ; // Moving to new level k++; // Traversing rightmost unvisited // element in path as we // move up to down while (k < maxLevel) { j = nodes[k].size() - 1; cout << nodes[k][j - path] << " " ; k++; } j = nodes[k].size() - 1; if (k > path) for (j -= path; j >= 0; j--) cout << nodes[k][j] << " " ; // Setting value of new maximum // level upto which we have to traverse // next time maxLevel--; // Updating from which level to // start new path k--; path++; flag = !flag; } else { // Traversing each element of remaining // last level from left to right int j = nodes[k].size() - 1; for (j = 0; j < nodes[k].size() - path; j++) cout << nodes[k][j] << " " ; // Decrementing value of Max level maxLevel--; k--; // Traversing rightmost unvisited // element in path as we // move down to up while (k > path) { int j = nodes[k].size() - 1; cout << nodes[k][j - path] << " " ; k--; } j = nodes[k].size() - 1; if (k == path) for (j -= path; j >= 0; j--) cout << nodes[k][j] << " " ; path++; // Updating the level number from which // a new cycle has to be started k++; flag = !flag; } } } // Driver code int main() { // Initialising the above mentioned // complete binary tree for ( int i = 1; i <= 5; i++) { // Adding edge to a binary tree addEdge(i, 2 * i); addEdge(i, 2 * i + 1); } // Calling modified bfs function bfs(1); display(); return 0; } |
Java
// Java program to print sideways // traversal of complete binary tree import java.util.*; class GFG { static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } static int sz = ( int ) 1e5; static int maxLevel = 0 ; // Adjacency list representation // of the tree static Vector<Integer> []tree = new Vector[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 Vector<Integer> []nodes = new Vector[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<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.isEmpty()) { pair p = qu.peek(); // Dequeue a vertex from queue qu.remove(); 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.add( new pair( child, p.first )); level[child] = level[p.first] + 1 ; maxLevel = Math.max(maxLevel, level[child]); nodes[level[child]].add(child); } } } } // Utility Function to display the pattern static void display() { // k represents the level no. // cycle represents how many // cycles has been completed int k = 0 , path = 0 ; int condn = (maxLevel) / 2 + 1 ; boolean flag = true ; // While there are nodes left to traverse while (condn-- > 0 ) { if (flag) { // Traversing whole level from // left to right int j = nodes[k].size() - 1 ; for (j = 0 ; j < nodes[k].size() - path; j++) System.out.print(nodes[k].get(j)+ " " ); // Moving to new level k++; // Traversing rightmost unvisited // element in path as we // move up to down while (k < maxLevel) { j = nodes[k].size() - 1 ; System.out.print(nodes[k].get(j - path)+ " " ); k++; } j = nodes[k].size() - 1 ; if (k > path) for (j -= path; j >= 0 ; j--) System.out.print(nodes[k].get(j)+ " " ); // Setting value of new maximum // level upto which we have to traverse // next time maxLevel--; // Updating from which level to // start new path k--; path++; flag = !flag; } else { // Traversing each element of remaining // last level from left to right int j = nodes[k].size() - 1 ; for (j = 0 ; j < nodes[k].size() - path; j++) System.out.print(nodes[k].get(j)+ " " ); // Decrementing value of Max level maxLevel--; k--; // Traversing rightmost unvisited // element in path as we // move down to up while (k > path) { int c = nodes[k].size() - 1 ; System.out.print(nodes[k].get(c - path)+ " " ); k--; } j = nodes[k].size() - 1 ; if (k == path) for (j -= path; j >= 0 ; j--) System.out.print(nodes[k].get(j)+ " " ); path++; // Updating the level number from which // a new cycle has to be started k++; flag = !flag; } } } // Driver code public static void main(String[] args) { for ( int i = 0 ; i < tree.length; i++) { tree[i] = new Vector<>(); nodes[i] = new Vector<>(); } // Initialising the above mentioned // complete binary tree for ( int i = 1 ; i <= 5 ; i++) { // Adding edge to a binary tree addEdge(i, 2 * i); addEdge(i, 2 * i + 1 ); } // Calling modified bfs function bfs( 1 ); display(); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to print sideways # traversal of complete binary tree 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): # 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 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 (vis[child] = = False ): qu.append([child, p[ 0 ]]) level[child] = level[p[ 0 ]] + 1 maxLevel = max (maxLevel, level[child]) nodes[level[child]].append(child) # Utility Function to display the pattern def display(): global maxLevel # k represents the level no. # cycle represents how many # cycles has been completed k = 0 path = 0 condn = (maxLevel) / / 2 + 1 flag = True # While there are nodes left to traverse while (condn): if (flag): # Traversing whole level from # left to right j = len (nodes[k]) - 1 for j in range ( len (nodes[k]) - path): print (nodes[k][j],end = " " ) # Moving to new level k + = 1 # Traversing rightmost unvisited # element in path as we # move up to down while (k < maxLevel): j = len (nodes[k]) - 1 print (nodes[k][j - path], end = " " ) k + = 1 j = len (nodes[k]) - 1 if (k > path): while j > = 0 : j - = path print (nodes[k][j], end = " " ) j - = 1 # Setting value of new maximum # level upto which we have to traverse # next time maxLevel - = 1 # Updating from which level to # start new path k - = 1 path + = 1 flag = not flag else : # Traversing each element of remaining # last level from left to right j = len (nodes[k]) - 1 for j in range ( len (nodes[k]) - path): print (nodes[k][j], end = " " ) # Decrementing value of Max level maxLevel - = 1 k - = 1 # Traversing rightmost unvisited # element in path as we # move down to up while (k > path): j = len (nodes[k]) - 1 print (nodes[k][j - path], end = " " ) k - = 1 j = len (nodes[k]) - 1 if (k = = path): while j > = 0 : j - = path print (nodes[k][j],end = " " ) j - = 1 path + = 1 # Updating the level number from which # a new cycle has to be started k + = 1 flag = not flag condn - = 1 # Driver code if __name__ = = '__main__' : # Initialising the above mentioned # complete binary tree for i in range ( 1 , 6 ): # Adding edge to a binary tree addEdge(i, 2 * i) addEdge(i, 2 * i + 1 ) # Calling modified bfs function bfs( 1 ) display() # This code is contributed by mohit kumar 29 |
C#
// C# program to print sideways // traversal of complete binary tree using System; using System.Collections.Generic; class GFG { class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } static int sz = ( int ) 1e5; static int maxLevel = 0; // Adjacency list representation // of the tree static List< int > []tree = new List< int >[sz + 1]; // Boolean array to mark all the // vertices which are visited static bool []vis = new bool [sz + 1]; // int 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 List< int > []nodes = new List< int >[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<pair> qu = new Queue<pair>(); // Push root node in the front of // the queue and mark as visited qu.Enqueue( new pair( node, 0 )); nodes[0].Add(node); vis[node] = true ; level[1] = 0; while (qu.Count != 0) { pair p = qu.Peek(); // Dequeue a vertex from queue qu.Dequeue(); vis[p.first] = 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.first]) { if (!vis[child]) { qu.Enqueue( new pair( child, p.first )); level[child] = level[p.first] + 1; maxLevel = Math.Max(maxLevel, level[child]); nodes[level[child]].Add(child); } } } } // Utility Function to display the pattern static void display() { // k represents the level no. // cycle represents how many // cycles has been completed int k = 0, path = 0; int condn = (maxLevel) / 2 + 1; bool flag = true ; // While there are nodes left to traverse while (condn-- > 0) { if (flag) { // Traversing whole level from // left to right int j = nodes[k].Count - 1; for (j = 0; j < nodes[k].Count - path; j++) Console.Write(nodes[k][j]+ " " ); // Moving to new level k++; // Traversing rightmost unvisited // element in path as we // move up to down while (k < maxLevel) { j = nodes[k].Count - 1; Console.Write(nodes[k][j - path]+ " " ); k++; } j = nodes[k].Count - 1; if (k > path) for (j -= path; j >= 0; j--) Console.Write(nodes[k][j]+ " " ); // Setting value of new maximum // level upto which we have to traverse // next time maxLevel--; // Updating from which level to // start new path k--; path++; flag = !flag; } else { // Traversing each element of remaining // last level from left to right int j = nodes[k].Count - 1; for (j = 0; j < nodes[k].Count - path; j++) Console.Write(nodes[k][j]+ " " ); // Decrementing value of Max level maxLevel--; k--; // Traversing rightmost unvisited // element in path as we // move down to up while (k > path) { int c = nodes[k].Count - 1; Console.Write(nodes[k]+ " " ); k--; } j = nodes[k].Count - 1; if (k == path) for (j -= path; j >= 0; j--) Console.Write(nodes[k][j]+ " " ); path++; // Updating the level number from which // a new cycle has to be started k++; flag = !flag; } } } // Driver code public static void Main(String[] args) { for ( int i = 0; i < tree.Length; i++) { tree[i] = new List< int >(); nodes[i] = new List< int >(); } // Initialising the above mentioned // complete binary tree for ( int i = 1; i <= 5; i++) { // Adding edge to a binary tree addEdge(i, 2 * i); addEdge(i, 2 * i + 1); } // Calling modified bfs function bfs(1); display(); } } // This code contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to print sideways // traversal of complete binary tree let sz = 1e5; 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-First Function function bfs(node) { // Create a queue of {child, parent} 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[0]; // Dequeue a vertex from queue qu.shift(); vis[p[0]] = true ; // Get all adjacent vertices of the dequeued // vertex s. If any adjacent has not // been visited then enqueue 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]); } } } } // Utility Function to display the pattern function display() { // k represents the level no. // cycle represents how many // cycles has been completed let k = 0, path = 0; let condn = Math.floor((maxLevel) / 2) + 1; let flag = true ; // While there are nodes left to traverse while (condn-- > 0) { if (flag) { // Traversing whole level from // left to right let j = nodes[k].length - 1; for (j = 0; j < nodes[k].length - path; j++) document.write(nodes[k][j]+ " " ); // Moving to new level k++; // Traversing rightmost unvisited // element in path as we // move up to down while (k < maxLevel) { j = nodes[k].length - 1; document.write(nodes[k][j - path]+ " " ); k++; } j = nodes[k].length - 1; if (k > path) for (j -= path; j >= 0; j--) document.write(nodes[k][j]+ " " ); // Setting value of new maximum // level upto which we have to traverse // next time maxLevel--; // Updating from which level to // start new path k--; path++; flag = !flag; } else { // Traversing each element of remaining // last level from left to right let j = nodes[k].length - 1; for (j = 0; j < nodes[k].length - path; j++) document.write(nodes[k][j]+ " " ); // Decrementing value of Max level maxLevel--; k--; // Traversing rightmost unvisited // element in path as we // move down to up while (k > path) { let c = nodes[k].length - 1; document.write(nodes[k]+ " " ); k--; } j = nodes[k].length - 1; if (k == path) for (j -= path; j >= 0; j--) document.write(nodes[k][j]+ " " ); path++; // Updating the level number from which // a new cycle has to be started k++; flag = !flag; } } } // Driver code for (let i = 0; i < tree.length; i++) { tree[i] = []; nodes[i] = []; vis[i]= false ; level[i]=0; } // Initialising the above mentioned // complete binary tree for (let i = 1; i <= 5; i++) { // Adding edge to a binary tree addEdge(i, 2 * i); addEdge(i, 2 * i + 1); } // Calling modified bfs function bfs(1); display(); // This code is contributed by unknown2108 </script> |
Output:
1 3 7 11 10 9 8 4 5 6 2
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!