Print Binary Tree in 2-Dimensions
Given a Binary Tree, print it in two dimension.
Examples:
Input : Pointer to root of below tree
1
/ \
2 3
/ \ / \
4 5 6 7
Output :
7
3
6
1
5
2
4
We strongly recommend you to minimize your browser and try this yourself first.
If we take a closer look at the pattern, we can notice following.
- Rightmost node is printed in first line and leftmost node is printed in last line.
- Space count increases by a fixed amount at every level.
So we do a reverse inorder traversal (right – root – left) and print tree nodes. We increase space by a fixed amount at every level.
Below is the implementation.
C++
// C++ Program to print binary tree in 2D #include <bits/stdc++.h> using namespace std; #define COUNT 10 // A binary tree node class Node { public : int data; Node *left, *right; /* Constructor that allocates a new node with the given data and NULL left and right pointers. */ Node( int data) { this ->data = data; this ->left = NULL; this ->right = NULL; } }; // Function to print binary tree in 2D // It does reverse inorder traversal void print2DUtil(Node* root, int space) { // Base case if (root == NULL) return ; // Increase distance between levels space += COUNT; // Process right child first print2DUtil(root->right, space); // Print current node after space // count cout << endl; for ( int i = COUNT; i < space; i++) cout << " " ; cout << root->data << "\n" ; // Process left child print2DUtil(root->left, space); } // Wrapper over print2DUtil() void print2D(Node* root) { // Pass initial space count as 0 print2DUtil(root, 0); } // Driver code int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->left = new Node(12); root->right->left->right = new Node(13); root->right->right->left = new Node(14); root->right->right->right = new Node(15); print2D(root); return 0; } // This code is contributed by rathbhupendra |
C
// Program to print binary tree in 2D #include <malloc.h> #include <stdio.h> #define COUNT 10 // A binary tree node struct Node { int data; struct Node *left, *right; }; // Helper function to allocates a new node struct Node* newNode( int data) { struct Node* node = ( struct Node*) malloc ( sizeof ( struct Node)); node->data = data; node->left = node->right = NULL; return node; } // Function to print binary tree in 2D // It does reverse inorder traversal void print2DUtil( struct Node* root, int space) { // Base case if (root == NULL) return ; // Increase distance between levels space += COUNT; // Process right child first print2DUtil(root->right, space); // Print current node after space // count printf ( "\n" ); for ( int i = COUNT; i < space; i++) printf ( " " ); printf ( "%d\n" , root->data); // Process left child print2DUtil(root->left, space); } // Wrapper over print2DUtil() void print2D( struct Node* root) { // Pass initial space count as 0 print2DUtil(root, 0); } // Driver program to test above functions int main() { struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->left->left->left = newNode(8); root->left->left->right = newNode(9); root->left->right->left = newNode(10); root->left->right->right = newNode(11); root->right->left->left = newNode(12); root->right->left->right = newNode(13); root->right->right->left = newNode(14); root->right->right->right = newNode(15); print2D(root); return 0; } |
Java
// Java Program to print binary tree in 2D class GFG { static final int COUNT = 10 ; // A binary tree node static class Node { int data; Node left, right; /* Constructor that allocates a new node with the given data and null left and right pointers. */ Node( int data) { this .data = data; this .left = null ; this .right = null ; } }; // Function to print binary tree in 2D // It does reverse inorder traversal static void print2DUtil(Node root, int space) { // Base case if (root == null ) return ; // Increase distance between levels space += COUNT; // Process right child first print2DUtil(root.right, space); // Print current node after space // count System.out.print( "\n" ); for ( int i = COUNT; i < space; i++) System.out.print( " " ); System.out.print(root.data + "\n" ); // Process left child print2DUtil(root.left, space); } // Wrapper over print2DUtil() static void print2D(Node root) { // Pass initial space count as 0 print2DUtil(root, 0 ); } // Driver code public static void main(String args[]) { Node root = new Node( 1 ); root.left = new Node( 2 ); root.right = new Node( 3 ); root.left.left = new Node( 4 ); root.left.right = new Node( 5 ); root.right.left = new Node( 6 ); root.right.right = new Node( 7 ); root.left.left.left = new Node( 8 ); root.left.left.right = new Node( 9 ); root.left.right.left = new Node( 10 ); root.left.right.right = new Node( 11 ); root.right.left.left = new Node( 12 ); root.right.left.right = new Node( 13 ); root.right.right.left = new Node( 14 ); root.right.right.right = new Node( 15 ); print2D(root); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 Program to print binary tree in 2D COUNT = [ 10 ] # Binary Tree Node """ utility that allocates a newNode with the given key """ class newNode: # Construct to create a newNode def __init__( self , key): self .data = key self .left = None self .right = None # Function to print binary tree in 2D # It does reverse inorder traversal def print2DUtil(root, space): # Base case if (root = = None ): return # Increase distance between levels space + = COUNT[ 0 ] # Process right child first print2DUtil(root.right, space) # Print current node after space # count print () for i in range (COUNT[ 0 ], space): print (end = " " ) print (root.data) # Process left child print2DUtil(root.left, space) # Wrapper over print2DUtil() def print2D(root): # space=[0] # Pass initial space count as 0 print2DUtil(root, 0 ) # Driver Code if __name__ = = '__main__' : root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) root.right.left = newNode( 6 ) root.right.right = newNode( 7 ) root.left.left.left = newNode( 8 ) root.left.left.right = newNode( 9 ) root.left.right.left = newNode( 10 ) root.left.right.right = newNode( 11 ) root.right.left.left = newNode( 12 ) root.right.left.right = newNode( 13 ) root.right.right.left = newNode( 14 ) root.right.right.right = newNode( 15 ) print2D(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
C#
// C# Program to print binary tree in 2D using System; class GFG { static readonly int COUNT = 10; // A binary tree node public class Node { public int data; public Node left, right; /* Constructor that allocates a new node with the given data and null left and right pointers. */ public Node( int data) { this .data = data; this .left = null ; this .right = null ; } }; // Function to print binary tree in 2D // It does reverse inorder traversal static void print2DUtil(Node root, int space) { // Base case if (root == null ) return ; // Increase distance between levels space += COUNT; // Process right child first print2DUtil(root.right, space); // Print current node after space // count Console.Write( "\n" ); for ( int i = COUNT; i < space; i++) Console.Write( " " ); Console.Write(root.data + "\n" ); // Process left child print2DUtil(root.left, space); } // Wrapper over print2DUtil() static void print2D(Node root) { // Pass initial space count as 0 print2DUtil(root, 0); } // Driver code public static void Main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.left = new Node(12); root.right.left.right = new Node(13); root.right.right.left = new Node(14); root.right.right.right = new Node(15); print2D(root); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript Program to print binary tree in 2D let COUNT = 10; // A binary tree node class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Function to print binary tree in 2D // It does reverse inorder traversal function print2DUtil(root,space) { // Base case if (root == null ) return ; // Increase distance between levels space += COUNT; // Process right child first print2DUtil(root.right, space); // Print current node after space // count document.write( "<br>" ); for (let i = COUNT; i < space; i++) document.write( " " ); document.write(root.data + "\n" ); // Process left child print2DUtil(root.left, space); } // Wrapper over print2DUtil() function print2D(root) { // Pass initial space count as 0 print2DUtil(root, 0); } // Driver code let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.left = new Node(12); root.right.left.right = new Node(13); root.right.right.left = new Node(14); root.right.right.right = new Node(15); print2D(root); // This code is contributed by patel2127 </script> |
Output
15 7 14 3 13 6 12 1 11 5 10 2 9 4 8
Time Complexity : O(n) as use inorder traversal.
Space Complexity: O(log n)
Using preorder Traversal
C++
//C++ code for the above approach #include <bits/stdc++.h> using namespace std; class Treenode { public : int data; Treenode *left, *right; Treenode( int data) { this ->data = data; left = right = NULL; } }; class Tree { public : Treenode *root; Tree() { root = NULL; } }; int height(Treenode *root) { if (root == NULL) return 0; return max(height(root->left), height(root->right)) + 1; } int getcol( int h) { if (h == 1) return 1; return getcol(h - 1) + getcol(h - 1) + 1; } void printTree( int **M, Treenode *root, int col, int row, int height) { if (root == NULL) return ; M[row][col] = root->data; printTree(M, root->left, col - pow (2, height - 2), row + 1, height - 1); printTree(M, root->right, col + pow (2, height - 2), row + 1, height - 1); } void TreePrinter(Tree tree) { int h = height(tree.root); int col = getcol(h); int **M = new int *[h]; for ( int i = 0; i < h; i++) { M[i] = new int [col]; } printTree(M, tree.root, col / 2, 0, h); for ( int i = 0; i < h; i++) { for ( int j = 0; j < col; j++) { if (M[i][j] == 0) cout << " " << " " ; else cout << M[i][j] << " " ; } cout << endl; } } int main() { Tree myTree; myTree.root = new Treenode(1); myTree.root->left = new Treenode(2); myTree.root->right = new Treenode(3); myTree.root->left->left = new Treenode(4); myTree.root->left->right = new Treenode(5); myTree.root->right->left = new Treenode(6); myTree.root->right->right = new Treenode(7); TreePrinter(myTree); return 0; } |
Java
import java.util.*; class Treenode { int data; Treenode left, right; Treenode( int data) { this .data = data; left = right = null ; } } class Tree { Treenode root; Tree() { root = null ; } } public class Main { public static int height(Treenode root) { if (root == null ) return 0 ; return Math.max(height(root.left), height(root.right)) + 1 ; } public static int getcol( int h) { if (h == 1 ) return 1 ; return getcol(h - 1 ) + getcol(h - 1 ) + 1 ; } public static void printTree( int [][] M, Treenode root, int col, int row, int height) { if (root == null ) return ; M[row][col] = root.data; printTree(M, root.left, col - ( int )Math.pow( 2 , height - 2 ), row + 1 , height - 1 ); printTree(M, root.right, col + ( int )Math.pow( 2 , height - 2 ), row + 1 , height - 1 ); } public static void TreePrinter(Tree tree) { int h = height(tree.root); int col = getcol(h); int [][] M = new int [h][col]; printTree(M, tree.root, col / 2 , 0 , h); for ( int i = 0 ; i < h; i++) { for ( int j = 0 ; j < col; j++) { if (M[i][j] == 0 ) System.out.print( " " ); else System.out.print(M[i][j] + " " ); } System.out.println(); } } public static void main(String[] args) { Tree myTree = new Tree(); myTree.root = new Treenode( 1 ); myTree.root.left = new Treenode( 2 ); myTree.root.right = new Treenode( 3 ); myTree.root.left.left = new Treenode( 4 ); myTree.root.left.right = new Treenode( 5 ); myTree.root.right.left = new Treenode( 6 ); myTree.root.right.right = new Treenode( 7 ); TreePrinter(myTree); } } |
Python3
class Treenode: def __init__( self , data): self .data = data self .left = None self .right = None class Tree: def __init__( self ): self .root = None def height(root): if root is None : return 0 return max (height(root.left), height(root.right)) + 1 def getcol(h): if h = = 1 : return 1 return getcol(h - 1 ) + getcol(h - 1 ) + 1 def printTree(M, root, col, row, height): if root is None : return M[row][col] = root.data printTree(M, root.left, col - pow ( 2 , height - 2 ), row + 1 , height - 1 ) printTree(M, root.right, col + pow ( 2 , height - 2 ), row + 1 , height - 1 ) def TreePrinter(): h = height(myTree.root) col = getcol(h) M = [[ 0 for _ in range (col)] for __ in range (h)] printTree(M, myTree.root, col / / 2 , 0 , h) for i in M: for j in i: if j = = 0 : print ( " " , end = " " ) else : print (j, end = " " ) print ("") myTree = Tree() myTree.root = Treenode( 1 ) myTree.root.left = Treenode( 2 ) myTree.root.right = Treenode( 3 ) myTree.root.left.left = Treenode( 4 ) myTree.root.left.right = Treenode( 5 ) myTree.root.right.left = Treenode( 6 ) myTree.root.right.right = Treenode( 7 ) TreePrinter() ##This Code is By Sudhanshu Nand Kumar |
C#
using System; class TreeNode { public int data; public TreeNode left; public TreeNode right; public TreeNode( int data) { this .data = data; this .left = null ; this .right = null ; } } class Tree { public TreeNode root; public Tree() { this .root = null ; } } class Program { static int Height(TreeNode root) { if (root == null ) { return 0; } return Math.Max(Height(root.left), Height(root.right)) + 1; } static int GetCol( int h) { if (h == 1) { return 1; } return GetCol(h - 1) + GetCol(h - 1) + 1; } static void PrintTree( int [][] M, TreeNode root, int col, int row, int height) { if (root == null ) { return ; } M[row][col] = root.data; PrintTree(M, root.left, col - ( int )Math.Pow(2, height - 2), row + 1, height - 1); PrintTree(M, root.right, col + ( int )Math.Pow(2, height - 2), row + 1, height - 1); } static void TreePrinter() { Tree myTree = new Tree(); myTree.root = new TreeNode(1); myTree.root.left = new TreeNode(2); myTree.root.right = new TreeNode(3); myTree.root.left.left = new TreeNode(4); myTree.root.left.right = new TreeNode(5); myTree.root.right.left = new TreeNode(6); myTree.root.right.right = new TreeNode(7); int h = Height(myTree.root); int col = GetCol(h); int [][] M = new int [h][]; for ( int i = 0; i < h; i++) { M[i] = new int [col]; Array.Fill(M[i], 0); } PrintTree(M, myTree.root, col / 2, 0, h); for ( int i = 0; i < M.Length; i++) { string row = "" ; for ( int j = 0; j < M[i].Length; j++) { if (M[i][j] == 0) { row += " " ; } else { row += M[i][j] + " " ; } } Console.WriteLine(row); } } static void Main( string [] args) { TreePrinter(); } } |
Javascript
class TreeNode { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } class Tree { constructor() { this .root = null ; } } function height(root) { if (root === null ) { return 0; } return Math.max(height(root.left), height(root.right)) + 1; } function getCol(h) { if (h === 1) { return 1; } return getCol(h - 1) + getCol(h - 1) + 1; } function printTree(M, root, col, row, height) { if (root === null ) { return ; } M[row][col] = root.data; printTree(M, root.left, col - Math.pow(2, height - 2), row + 1, height - 1); printTree(M, root.right, col + Math.pow(2, height - 2), row + 1, height - 1); } function treePrinter() { const myTree = new Tree(); myTree.root = new TreeNode(1); myTree.root.left = new TreeNode(2); myTree.root.right = new TreeNode(3); myTree.root.left.left = new TreeNode(4); myTree.root.left.right = new TreeNode(5); myTree.root.right.left = new TreeNode(6); myTree.root.right.right = new TreeNode(7); const h = height(myTree.root); const col = getCol(h); const M = new Array(h).fill().map(() => new Array(col).fill(0)); printTree(M, myTree.root, Math.floor(col / 2), 0, h); for (let i = 0; i < M.length; i++) { let row= "" ; for (let j = 0; j < M[i].length; j++) { if (M[i][j] === 0) { row = row + " " ; } else { row= row +M[i][j] + " " ; } } console.log(row); } } treePrinter(); |
Output
1 2 3 4 5 6 7
Another solution using level order traversal:
C++
#include <cmath> #include <iostream> #include <queue> using namespace std; class Node { public : int data; Node* left; Node* right; Node( int data) { this ->data = data; left = right = nullptr; } }; void printSpace( double n, Node* removed) { for (; n > 0; n--) { cout << "\t" ; } if (removed == nullptr) { cout << " " ; } else { cout << removed->data; } } int heightOfTree(Node* root) { if (root == nullptr) { return 0; } return 1 + max(heightOfTree(root->left), heightOfTree(root->right)); } void printBinaryTree(Node* root) { queue<Node*> treeLevel, temp; treeLevel.push(root); int counter = 0; int height = heightOfTree(root) - 1; double numberOfElements = pow (2, (height + 1)) - 1; while (counter <= height) { Node* removed = treeLevel.front(); treeLevel.pop(); if (temp.empty()) { printSpace(numberOfElements / pow (2, counter + 1), removed); } else { printSpace(numberOfElements / pow (2, counter), removed); } if (removed == nullptr) { temp.push(nullptr); temp.push(nullptr); } else { temp.push(removed->left); temp.push(removed->right); } if (treeLevel.empty()) { cout << endl << endl; treeLevel = temp; while (!temp.empty()) { temp.pop(); } counter++; } } } int main() { Node* root = new Node(1); Node* temp = nullptr; temp = new Node(2); root->left = temp; temp = new Node(3); root->right = temp; temp = new Node(4); root->left->left = temp; temp = new Node(5); root->left->right = temp; temp = new Node(6); root->right->left = temp; temp = new Node(7); root->right->right = temp; temp = new Node(8); root->left->left->left = temp; temp = new Node(9); root->left->left->right = temp; temp = new Node(10); root->left->right->left = temp; temp = new Node(11); root->left->right->right = temp; temp = new Node(12); root->right->left->left = temp; temp = new Node(13); root->right->left->right = temp; temp = new Node(14); root->right->right->left = temp; temp = new Node(15); root->right->right->right = temp; printBinaryTree(root); return 0; } |
Java
import java.util.LinkedList; public class Tree1 { public static void main(String[] args) { Tree1.Node root = new Tree1.Node( 1 ); Tree1.Node temp = null ; temp = new Tree1.Node( 2 ); root.left = temp; temp = new Tree1.Node( 3 ); root.right = temp; temp = new Tree1.Node( 4 ); root.left.left = temp; temp = new Tree1.Node( 5 ); root.left.right = temp; temp = new Tree1.Node( 6 ); root.right.left = temp; temp = new Tree1.Node( 7 ); root.right.right = temp; temp = new Tree1.Node( 8 ); root.left.left.left = temp; temp = new Tree1.Node( 9 ); root.left.left.right = temp; temp = new Tree1.Node( 10 ); root.left.right.left = temp; temp = new Tree1.Node( 11 ); root.left.right.right = temp; temp = new Tree1.Node( 12 ); root.right.left.left = temp; temp = new Tree1.Node( 13 ); root.right.left.right = temp; temp = new Tree1.Node( 14 ); root.right.right.left = temp; temp = new Tree1.Node( 15 ); root.right.right.right = temp; printBinaryTree(root); } public static class Node { public Node( int data) { this .data = data; } int data; Node left; Node right; } public static void printBinaryTree(Node root) { LinkedList<Node> treeLevel = new LinkedList<Node>(); treeLevel.add(root); LinkedList<Node> temp = new LinkedList<Node>(); int counter = 0 ; int height = heightOfTree(root) - 1 ; // System.out.println(height); double numberOfElements = (Math.pow( 2 , (height + 1 )) - 1 ); // System.out.println(numberOfElements); while (counter <= height) { Node removed = treeLevel.removeFirst(); if (temp.isEmpty()) { printSpace(numberOfElements / Math.pow( 2 , counter + 1 ), removed); } else { printSpace(numberOfElements / Math.pow( 2 , counter), removed); } if (removed == null ) { temp.add( null ); temp.add( null ); } else { temp.add(removed.left); temp.add(removed.right); } if (treeLevel.isEmpty()) { System.out.println( "" ); System.out.println( "" ); treeLevel = temp; temp = new LinkedList<>(); counter++; } } } public static void printSpace( double n, Node removed) { for (; n > 0 ; n--) { System.out.print( "\t" ); } if (removed == null ) { System.out.print( " " ); } else { System.out.print(removed.data); } } public static int heightOfTree(Node root) { if (root == null ) { return 0 ; } return 1 + Math.max(heightOfTree(root.left), heightOfTree(root.right)); } } |
Python3
class Node: def __init__( self , data): self .data = data self .left = None self .right = None # This function prints space characters to # format the output of the binary tree. # It takes in a number of spaces to print (n), # and a Node pointer to print instead of # a space if one is provided (removed). def print_space(n, removed): for i in range (n): print ( "\t" , end = "") if removed is None : print ( " " , end = "") else : print (removed.data, end = "") def height_of_tree(root): if root is None : return 0 return 1 + max (height_of_tree(root.left), height_of_tree(root.right)) def print_binary_tree(root): tree_level = [] temp = [] tree_level.append(root) counter = 0 height = height_of_tree(root) - 1 number_of_elements = 2 * * (height + 1 ) - 1 while counter < = height: removed = tree_level.pop( 0 ) if len (temp) = = 0 : print_space( int (number_of_elements / ( 2 * * (counter + 1 ))), removed) else : print_space( int (number_of_elements / ( 2 * * counter)), removed) if removed is None : temp.append( None ) temp.append( None ) else : temp.append(removed.left) temp.append(removed.right) if len (tree_level) = = 0 : print ( "\n" ) tree_level = temp temp = [] counter + = 1 root = Node( 1 ) temp = Node( 2 ) root.left = temp temp = Node( 3 ) root.right = temp temp = Node( 4 ) root.left.left = temp temp = Node( 5 ) root.left.right = temp temp = Node( 6 ) root.right.left = temp temp = Node( 7 ) root.right.right = temp temp = Node( 8 ) root.left.left.left = temp temp = Node( 9 ) root.left.left.right = temp temp = Node( 10 ) root.left.right.left = temp temp = Node( 11 ) root.left.right.right = temp temp = Node( 12 ) root.right.left.left = temp temp = Node( 13 ) root.right.left.right = temp temp = Node( 14 ) root.right.right.left = temp temp = Node( 15 ) root.right.right.right = temp print_binary_tree(root) |
C#
using System; using System.Collections.Generic; class Node { public int data; public Node left; public Node right; public Node( int data) { this .data = data; left = right = null ; } } class BinaryTreePrinter { // Function to print spaces or node data based on position static void PrintSpace( double n, Node removed) { for (; n > 0; n--) { Console.Write( "\t" ); } if (removed == null ) { Console.Write( " " ); } else { Console.Write(removed.data); } } // Function to calculate the height of the tree static int HeightOfTree(Node root) { if (root == null ) { return 0; } return 1 + Math.Max(HeightOfTree(root.left), HeightOfTree(root.right)); } // Function to print a binary tree static void PrintBinaryTree(Node root) { Queue<Node> treeLevel = new Queue<Node>(); Queue<Node> temp = new Queue<Node>(); treeLevel.Enqueue(root); int counter = 0; int height = HeightOfTree(root) - 1; double numberOfElements = Math.Pow(2, (height + 1)) - 1; while (counter <= height) { Node removed = treeLevel.Dequeue(); if (temp.Count == 0) { PrintSpace(numberOfElements / Math.Pow(2, counter + 1), removed); } else { PrintSpace(numberOfElements / Math.Pow(2, counter), removed); } if (removed == null ) { temp.Enqueue( null ); temp.Enqueue( null ); } else { temp.Enqueue(removed.left); temp.Enqueue(removed.right); } if (treeLevel.Count == 0) { Console.WriteLine( "\n\n" ); treeLevel = new Queue<Node>(temp); temp.Clear(); counter++; } } } static void Main( string [] args) { Node root = new Node(1); Node temp = null ; temp = new Node(2); root.left = temp; temp = new Node(3); root.right = temp; temp = new Node(4); root.left.left = temp; temp = new Node(5); root.left.right = temp; temp = new Node(6); root.right.left = temp; temp = new Node(7); root.right.right = temp; temp = new Node(8); root.left.left.left = temp; temp = new Node(9); root.left.left.right = temp; temp = new Node(10); root.left.right.left = temp; temp = new Node(11); root.left.right.right = temp; temp = new Node(12); root.right.left.left = temp; temp = new Node(13); root.right.left.right = temp; temp = new Node(14); root.right.right.left = temp; temp = new Node(15); root.right.right.right = temp; PrintBinaryTree(root); } } |
Javascript
class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // This function prints space characters to format the output of the binary tree. // It takes in a number of spaces to print (n), and a Node pointer to print instead of a space if one is provided (removed). function printSpace(n, removed) { for (let i = 0; i < n; i++) { process.stdout.write( "\t" ); } if (removed == null ) { process.stdout.write( " " ); } else { process.stdout.write(removed.data.toString()); } } function heightOfTree(root) { if (root == null ) { return 0; } return 1 + Math.max(heightOfTree(root.left), heightOfTree(root.right)); } function printBinaryTree(root) { let treeLevel = [], temp = []; treeLevel.push(root); let counter = 0; let height = heightOfTree(root) - 1; let numberOfElements = Math.pow(2, (height + 1)) - 1; while (counter <= height) { let removed = treeLevel.shift(); if (temp.length == 0) { printSpace(numberOfElements / Math.pow(2, counter + 1), removed); } else { printSpace(numberOfElements / Math.pow(2, counter), removed); } if (removed == null ) { temp.push( null ); temp.push( null ); } else { temp.push(removed.left); temp.push(removed.right); } if (treeLevel.length == 0) { console.log( "\n" ); treeLevel = temp; temp = []; counter++; } } } let root = new Node(1); let temp = null ; temp = new Node(2); root.left = temp; temp = new Node(3); root.right = temp; temp = new Node(4); root.left.left = temp; temp = new Node(5); root.left.right = temp; temp = new Node(6); root.right.left = temp; temp = new Node(7); root.right.right = temp; temp = new Node(8); root.left.left.left = temp; temp = new Node(9); root.left.left.right = temp; temp = new Node(10); root.left.right.left = temp; temp = new Node(11); root.left.right.right = temp; temp = new Node(12); root.right.left.left = temp; temp = new Node(13); root.right.left.right = temp; temp = new Node(14); root.right.right.left = temp; temp = new Node(15); root.right.right.right = temp; printBinaryTree(root); |
Output
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Contact Us