Print Binary Tree in 2D

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

1. The first line prints the rightmost node, while the last line prints the leftmost node. 
2. Every level has a constant increase in the number of spaces.
3. Therefore, we traverse the tree in reverse in-order (right - root - left) and print the tree nodes.
4. At every level, we add a fixed amount of space.
5. Do it until every node is printed in that order.
6. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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).