Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Reverse In-Order Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time complexity 
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
Where are binary trees used?
3.2.
Which algorithm can we use to print binary tree?
3.3.
What is in-order traversal?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Print Binary Tree in 2D

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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;
}

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)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Where are binary trees used?

In spreadsheets like Microsoft Excel, the binary tree data structure is typically used. Indexing for Segmented Databases is done using Binary Tree.

Which algorithm can we use to print binary tree?

Recursion is the most straightforward approach to implement the in-order traversal algorithm. Recursion is the natural choice for solving a tree-based problem because the binary tree is a recursive data structure.

What is in-order traversal?

Recursively process the left subtree, the root, and then the right subtree to process all of the nodes in a tree.

Conclusion

In this blog, we discussed a coding problem involving reverse in-order approach to Print Binary Tree in 2D. We discussed the time and space complexity of the approach as well.

Hope you liked the blog and it has added some knowledge to your life. Please have a look at these similar problems to learn more: Level Order Traversal, Specific LOTReverse Level Order TraversalDisjoint-set data structure.

If you want to practice problems on binary trees, you can refer to these links:

  1.  LCA of three Nodes,
  2.  Longest Univalue Path
  3. Boundary Traversal of Binary Tree
  4. Time To Burn Tree, and many more at Coding Ninjas Studio.
     

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Do upvote our blogs if you find them helpful and engaging!

Happy Coding!

Previous article
Check if a Binary Tree has Duplicate Values
Next article
Print nodes at k distance from root
Live masterclass