Print a two-dimensional view of a binary tree
Write an efficient algorithm to print the two-dimensional view of a binary tree.
For example, the above binary tree can be displayed as:
7
3
6
1
5
2
4
One can notice the following things in the above binary tree illustration:
- The rightmost node is printed in the first line.
- The leftmost node is printed in the last line.
- A fixed amount of space is increased at each level.
Consider the following C++, Java, and Python code, which performs a reverse inorder traversal and print nodes by increasing space by a fixed amount at every level. It serves as an excellent utility function for printing the binary tree.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <utility> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Utility function to print the two-dimensional view of a binary tree using // reverse inorder traversal void printBinaryTree(Node* root, int space = 0, int height = 10) { // Base case if (root == nullptr) { return; } // increase distance between levels space += height; // print right child first printBinaryTree(root->right, space); cout << endl; // print the current node after padding with spaces for (int i = height; i < space; i++) { cout << ' '; } cout << root->data; // print left child cout << endl; printBinaryTree(root->left, space); } int main() { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 7 */ 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); // print binary tree printBinaryTree(root); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Utility function to print the two-dimensional view of a binary tree using // reverse inorder traversal public static void printBinaryTree(Node root, int space, int height) { // Base case if (root == null) { return; } // increase distance between levels space += height; // print right child first printBinaryTree(root.right, space, height); System.out.println(); // print the current node after padding with spaces for (int i = height; i < space; i++) { System.out.print(' '); } System.out.print(root.data); // print left child System.out.println(); printBinaryTree(root.left, space, height); } public static void main(String[] args) { /* Construct the following tree 1 / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 7 */ 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); // print binary tree int space = 0, height = 10; printBinaryTree(root, space, height); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
# A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Utility function to print the two-dimensional view of a binary tree using # reverse inorder traversal def printBinaryTree(root, space, height): # Base case if root is None: return # increase distance between levels space += height # print right child first printBinaryTree(root.right, space, height) print() # print the current node after padding with spaces for i in range(height, space): print(' ', end='') print(root.data, end='') # print left child print() printBinaryTree(root.left, space, height) if __name__ == '__main__': ''' Construct the following tree 1 / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 7 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) # print binary tree space = 0 height = 10 printBinaryTree(root, space, height) |
Author: Aditya Goel
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)