Given an N-ary tree, the task is to print the N-ary tree graphically.
Graphical Representation of Tree: A representation of tree in which the root is printed in a line and the children nodes are printed in subsequent lines with some amount of indentation.
Examples:
Input: 0 / | \ / | \ 1 2 3 / \ / | \ 4 5 6 7 8 | 9 Output: 0 +--- 1 | +--- 4 | +--- 5 +--- 2 +--- 3 +--- 6 +--- 7 | +--- 9 +--- 8
Approach: The idea is to traverse the N-ary Tree using DFS Traversal to traverse the nodes and explore its children nodes until all the nodes are visited and then similarly, traverse the sibling nodes.
The step-by-step algorithm for the above approach is described below –
- Initialize a variable to store the current depth of the node, for the root node the depth is 0.
- Declare a boolean array to store the current exploring depths and initially mark all of them to False.
- If the current node is a root node that is the depth of the node is 0, then simply print the data of the node.
- Otherwise, Iterate over a loop from 1 to the current depth of node and print, ‘|’ and three spaces for each of the exploring depth and for non-exploring depth print three spaces only.
- Print the current value of the node and move the output pointer to the next line.
- If the current node is the last node of that depth then mark that depth as non-exploring.
- Similarly, explore all the child nodes with the recursive call.
Below is the implementation of the above approach:
C++
// C++ implementation to print // N-ary Tree graphically #include <iostream> #include <list> #include <vector> using namespace std; // Structure of the node struct tnode { int n; list<tnode*> root; tnode( int data) : n(data) { } }; // Function to print the // N-ary tree graphically void printNTree(tnode* x, vector< bool > flag, int depth = 0, bool isLast = false ) { // Condition when node is None if (x == NULL) return ; // Loop to print the depths of the // current node for ( int i = 1; i < depth; ++i) { // Condition when the depth // is exploring if (flag[i] == true ) { cout << "| " << " " << " " << " " ; } // Otherwise print // the blank spaces else { cout << " " << " " << " " << " " ; } } // Condition when the current // node is the root node if (depth == 0) cout << x->n << '\n' ; // Condition when the node is // the last node of // the exploring depth else if (isLast) { cout << "+--- " << x->n << '\n' ; // No more childrens turn it // to the non-exploring depth flag[depth] = false ; } else { cout << "+--- " << x->n << '\n' ; } int it = 0; for ( auto i = x->root.begin(); i != x->root.end(); ++i, ++it) // Recursive call for the // children nodes printNTree(*i, flag, depth + 1, it == (x->root.size()) - 1); flag[depth] = true ; } // Function to form the Tree and // print it graphically void formAndPrintTree(){ int nv = 10; tnode r(0), n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8), n9(9); // Array to keep track // of exploring depths vector< bool > flag(nv, true ); // Tree Formation r.root.push_back(&n1); n1.root.push_back(&n4); n1.root.push_back(&n5); r.root.push_back(&n2); r.root.push_back(&n3); n3.root.push_back(&n6); n3.root.push_back(&n7); n7.root.push_back(&n9); n3.root.push_back(&n8); printNTree(&r, flag); } // Driver Code int main( int argc, char const * argv[]) { // Function Call formAndPrintTree(); return 0; } |
Java
// Java implementation to print // N-ary Tree graphically import java.util.*; class GFG{ // Structure of the node static class tnode { int n; Vector<tnode> root = new Vector<>(); tnode( int data) { this .n = data; } }; // Function to print the // N-ary tree graphically static void printNTree(tnode x, boolean [] flag, int depth, boolean isLast ) { // Condition when node is None if (x == null ) return ; // Loop to print the depths of the // current node for ( int i = 1 ; i < depth; ++i) { // Condition when the depth // is exploring if (flag[i] == true ) { System.out.print( "| " + " " + " " + " " ); } // Otherwise print // the blank spaces else { System.out.print( " " + " " + " " + " " ); } } // Condition when the current // node is the root node if (depth == 0 ) System.out.println(x.n); // Condition when the node is // the last node of // the exploring depth else if (isLast) { System.out.print( "+--- " + x.n + '\n' ); // No more childrens turn it // to the non-exploring depth flag[depth] = false ; } else { System.out.print( "+--- " + x.n + '\n' ); } int it = 0 ; for (tnode i : x.root) { ++it; // Recursive call for the // children nodes printNTree(i, flag, depth + 1 , it == (x.root.size()) - 1 ); } flag[depth] = true ; } // Function to form the Tree and // print it graphically static void formAndPrintTree(){ int nv = 10 ; tnode r = new tnode( 0 ); tnode n1 = new tnode( 1 ); tnode n2 = new tnode( 2 ); tnode n3 = new tnode( 3 ); tnode n4 = new tnode( 4 ); tnode n5 = new tnode( 5 ); tnode n6 = new tnode( 6 ); tnode n7 = new tnode( 7 ); tnode n8 = new tnode( 8 ); tnode n9 = new tnode( 9 ); // Array to keep track // of exploring depths boolean [] flag = new boolean [nv]; Arrays.fill(flag, true ); // Tree Formation r.root.add(n1); n1.root.add(n4); n1.root.add(n5); r.root.add(n2); r.root.add(n3); n3.root.add(n6); n3.root.add(n7); n7.root.add(n9); n3.root.add(n8); printNTree(r, flag, 0 , false ); } // Driver Code public static void main(String[] args) { // Function Call formAndPrintTree(); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 implementation to print N-ary Tree graphically # Structure of the node class tnode: def __init__( self , data): self .n = data self .root = [] # Function to print the # N-ary tree graphically def printNTree(x,flag,depth,isLast): # Condition when node is None if x = = None : return # Loop to print the depths of the # current node for i in range ( 1 , depth): # Condition when the depth # is exploring if flag[i]: print ( "| " ," ", " ", " ", end = " ") # Otherwise print # the blank spaces else : print ( " " , " ", " ", " ", end = " ") # Condition when the current # node is the root node if depth = = 0 : print (x.n) # Condition when the node is # the last node of # the exploring depth elif isLast: print ( "+---" , x.n) # No more childrens turn it # to the non-exploring depth flag[depth] = False else : print ( "+---" , x.n) it = 0 for i in x.root: it + = 1 # Recursive call for the # children nodes printNTree(i, flag, depth + 1 , it = = ( len (x.root) - 1 )) flag[depth] = True # Function to form the Tree and # print it graphically def formAndPrintTree(): nv = 10 r = tnode( 0 ) n1 = tnode( 1 ) n2 = tnode( 2 ) n3 = tnode( 3 ) n4 = tnode( 4 ) n5 = tnode( 5 ) n6 = tnode( 6 ) n7 = tnode( 7 ) n8 = tnode( 8 ) n9 = tnode( 9 ) # Array to keep track # of exploring depths flag = [ True ] * (nv) # Tree Formation r.root.append(n1) n1.root.append(n4) n1.root.append(n5) r.root.append(n2) r.root.append(n3) n3.root.append(n6) n3.root.append(n7) n7.root.append(n9) n3.root.append(n8) printNTree(r, flag, 0 , False ) formAndPrintTree(); # This code is contributed by suresh07. |
C#
// C# implementation to print // N-ary Tree graphically using System; using System.Collections.Generic; class GFG { // Structure of the node public class tnode { public int n; public List<tnode> root = new List<tnode>(); public tnode( int data) { this .n = data; } }; // Function to print the // N-ary tree graphically static void printNTree(tnode x, bool [] flag, int depth, bool isLast ) { // Condition when node is None if (x == null ) return ; // Loop to print the depths of the // current node for ( int i = 1; i < depth; ++i) { // Condition when the depth // is exploring if (flag[i] == true ) { Console.Write( "| " + " " + " " + " " ); } // Otherwise print // the blank spaces else { Console.Write( " " + " " + " " + " " ); } } // Condition when the current // node is the root node if (depth == 0) Console.WriteLine(x.n); // Condition when the node is // the last node of // the exploring depth else if (isLast) { Console.Write( "+--- " + x.n + '\n' ); // No more childrens turn it // to the non-exploring depth flag[depth] = false ; } else { Console.Write( "+--- " + x.n + '\n' ); } int it = 0; foreach (tnode i in x.root) { ++it; // Recursive call for the // children nodes printNTree(i, flag, depth + 1, it == (x.root.Count) - 1); } flag[depth] = true ; } // Function to form the Tree and // print it graphically static void formAndPrintTree() { int nv = 10; tnode r = new tnode(0); tnode n1 = new tnode(1); tnode n2 = new tnode(2); tnode n3 = new tnode(3); tnode n4 = new tnode(4); tnode n5 = new tnode(5); tnode n6 = new tnode(6); tnode n7 = new tnode(7); tnode n8 = new tnode(8); tnode n9 = new tnode(9); // Array to keep track // of exploring depths bool [] flag = new bool [nv]; for ( int i = 0; i < nv; i++) flag[i] = true ; // Tree Formation r.root.Add(n1); n1.root.Add(n4); n1.root.Add(n5); r.root.Add(n2); r.root.Add(n3); n3.root.Add(n6); n3.root.Add(n7); n7.root.Add(n9); n3.root.Add(n8); printNTree(r, flag, 0, false ); } // Driver Code public static void Main(String[] args) { // Function Call formAndPrintTree(); } } // This code is contributed by aashish1995 |
Javascript
<script> // JavaScript implementation to print // N-ary Tree graphically // Structure of the node class tnode { constructor(data) { this .n = data; this .root=[]; } } // Function to print the // N-ary tree graphically function printNTree(x,flag,depth,isLast) { // Condition when node is None if (x == null ) return ; // Loop to print the depths of the // current node for (let i = 1; i < depth; ++i) { // Condition when the depth // is exploring if (flag[i] == true ) { document.write( "| " + "  " + "  " + "  " ); } // Otherwise print // the blank spaces else { document.write( "  " + "  " + "  " + "  " ); } } // Condition when the current // node is the root node if (depth == 0) document.write(x.n+ "<br>" ); // Condition when the node is // the last node of // the exploring depth else if (isLast) { document.write( "+--- " + x.n + '<br>' ); // No more childrens turn it // to the non-exploring depth flag[depth] = false ; } else { document.write( "+--- " + x.n + '<br>' ); } let it = 0; for (let i of x.root.values()) { ++it; // Recursive call for the // children nodes printNTree(i, flag, depth + 1, it == (x.root.length) - 1); } flag[depth] = true ; } // Function to form the Tree and // print it graphically function formAndPrintTree() { nv = 10; let r = new tnode(0); let n1 = new tnode(1); let n2 = new tnode(2); let n3 = new tnode(3); let n4 = new tnode(4); let n5 = new tnode(5); let n6 = new tnode(6); let n7 = new tnode(7); let n8 = new tnode(8); let n9 = new tnode(9); // Array to keep track // of exploring depths let flag = new Array(nv); for (let i=0;i<nv;i++) { flag[i]= true ; } // Tree Formation r.root.push(n1); n1.root.push(n4); n1.root.push(n5); r.root.push(n2); r.root.push(n3); n3.root.push(n6); n3.root.push(n7); n7.root.push(n9); n3.root.push(n8); printNTree(r, flag, 0, false ); } // Driver Code // Function Call formAndPrintTree(); // This code is contributed by unknown2108 </script> |
0 +--- 1 | +--- 4 | +--- 5 +--- 2 +--- 3 +--- 6 +--- 7 | +--- 9 +--- 8
Performance Analysis:
- Time Complexity: In the above-given approach, there is a recursive call to explore all the vertices which takes O(V) time. Therefore, the time complexity for this approach will be O(V).
- Auxiliary Space Complexity: In the above-given approach, there is extra space used to store the exploring depths. Therefore, the auxiliary space complexity for the above approach will be O(V)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!