Problem
Given a binary tree, the task is to print the two-dimensional view of it.
Sample Input
1 / \ 9 3 / \ / \ 2 5 6 10
Sample Output:
10 3 6 1 5 9 2
Approach
This problem is based on the observations that we can make from the examples. Below are the observations:
1) Rightmost node of the tree is printed in the first line, and the leftmost node is printed in the last line.
2) Space count increases by a fixed quantity at every level. We need to do a reverse in-order traversal and print tree nodes. We increase space by a fixed amount at every level. The reverse in order will first explore the right subtree, then the root, and then the left subtree.
Complexity Analysis
The time complexity would be O(N), and the space complexity would also be O(N) due to the call stack.
C++ Programming
#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int val)
{
this->val = val;
this->left = this->right = nullptr;
}
};
void inOrder(TreeNode* root, int gap = 0, int height = 10)
{
// Base case
if (!root) {
return;
}
// increase the gap count
gap += height;
// print right child
inOrder(root->right, gap);
cout << endl;
// print the current node after gap
for (int i = height; i < gap; i++) {
cout << ' ';
}
cout << root->val;
// print left child
cout << endl;
inOrder(root->left, gap);
}
int main()
{
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(9);
root->right = new TreeNode(3);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(10);
inOrder(root);
return 0;
}
Output
10 3 6 1 5 9 2
Java Programming
class TreeNode
{
int val;
TreeNode left, right;
TreeNode(int val)
{
this.val = val;
this.left = this.right = null;
}
}
class Main
{
public static void inOrder(TreeNode root, int gap, int height)
{
// Base case
if (root == null) {
return;
}
// increase the gap
gap += height;
// print right child
inOrder(root.right, gap, height);
System.out.println();
// print the current node after spaces
for (int i = height; i < gap; i++) {
System.out.print(' ');
}
System.out.print(root.val);
// print left child
System.out.println();
inOrder(root.left, gap, height);
}
public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(9);
root.right = new TreeNode(3);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(10);
int gap = 0, height = 10;
inOrder(root, gap, height);
}
}
Output
10 3 6 1 5 9 2
Python Programming
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inOrder(root, gap, height):
# Base case
if root is None:
return
# increase the gap
gap += height
# print right child
inOrder(root.right, gap, height)
print()
# print the current node
for i in range(height, gap):
print(' ', end='')
print(root.val, end='')
# print left child
print()
inOrder(root.left, gap, height)
root = TreeNode(1)
root.left = TreeNode(9)
root.right = TreeNode(3)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(10)
gap = 0
height = 10
inOrder(root, gap, height)
Output
10 3 6 1 5 9 2
People are also reading:
Leave a Comment on this Post