Introduction
Print binary tree in 2d is a binary tree problem. It is one of the most common SDE interview questions. It is asked by the interviewer when he wants to check the candidate’s understanding of the concept of binary tree and their implementation.
Problem Statement
Ninja gave us a binary tree in a particular order.
He assigned us a task to print that binary tree in two dimensions.
The task assigned by the ninja is a little bit confusing, let’s explore some sample problems to understand the task better.
Sample Examples
Example 1:
Output:
Example 2:
Output:
Reverse In-Order Approach
A modified form of inorder traversal called reverse inorder traversal is occasionally required to solve tree problems. With the exception of the subtree traverse order, the fundamental principle of reverse inorder traversal is the same as that of inorder traversal.
Algorithm
- The first line prints the rightmost node, while the last line prints the leftmost node.
- Every level has a constant increase in the number of spaces.
- Therefore, we traverse the tree in reverse in-order (right - root - left) and print the tree nodes.
- At every level, we add a fixed amount of space.
- Do it until every node is printed in that order.
- End
Implementation
#include <iostream>
#include <utility>
using namespace std;
// Data structure to store 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 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;
}
// now increase distance between levels
space += height;
// print the right child first
printBinaryTree(root->right, space);
cout << endl;
// print the current node after increasing with spaces
for (int i = height; i < space; i++) {
cout << ' ';
}
cout << root->data;
// print the left child
cout << endl;
printBinaryTree(root->left, space);
}
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);
// print binary tree
printBinaryTree(root);
return 0;
}
Output:
Time complexity
The time complexity of the reverse in-order approach is O(n), as we know, we are doing in-order traversal in reverse and the time complexity of doing in-order traversal is O(n).
Space Complexity
The space complexity depends upon the size of the recursion call stack i.e, maximum depth of the recursion or height of the tree(h). In this program, we have taken a balanced binary tree so h is equal to logn. Hence space complexity is O(logn).
In the worst case when our Binary Tree is highly unbalanced, the space complexity of the algorithm would be O(n).