In this tutorial, we are going to solve or make a solution to the Hackerrank Tree: Top View problem. so here we have given a pointer to the head or root node of a binary tree and we need to print the top view of the binary tree.
Problem solution in Python programming.
class Node: def __init__(self, info): self.info = info self.left = None self.right = None self.level = None def __str__(self): return str(self.info) class BinarySearchTree: def __init__(self): self.root = None def create(self, val): if self.root == None: self.root = Node(val) else: current = self.root while True: if val < current.info: if current.left: current = current.left else: current.left = Node(val) break elif val > current.info: if current.right: current = current.right else: current.right = Node(val) break else: break """ Node is defined as self.left (the left child of the node) self.right (the right child of the node) self.info (the value of the node) """ def topView(root): hm={} queue=[] queue.append((root,0)) while(queue): q=queue.pop(0) if q[1] not in hm: hm[q[1]]=q[0].info if q[0].left: queue.append((q[0].left,q[1]-1)) if q[0].right: queue.append((q[0].right,q[1]+1)) for k, v in sorted(hm.items()): print(str(v)+' ', end='') tree = BinarySearchTree() t = int(input()) arr = list(map(int, input().split())) for i in range(t): tree.create(arr[i]) topView(tree.root)
Problem solution in Java Programming.
import java.util.*; import java.io.*; class Node { Node left; Node right; int data; Node(int data) { this.data = data; left = null; right = null; } } class Solution { /* class Node int data; Node left; Node right; */ static class Pair{ public Node node; public int dist; public Pair(Node node, int dist){ this.node = node; this.dist = dist; } } public static void topView(Node root) { if(root == null) return; Map<Integer, Integer> mp = new TreeMap<>(); Queue<Pair> q = new LinkedList<Pair>(); q.add(new Pair(root, 0)); while(!q.isEmpty()){ Pair pair = q.poll(); Node node = pair.node; int dist = pair.dist; if(!mp.containsKey(dist)){ mp.put(dist, node.data); } if(node.left != null){ q.add(new Pair(node.left, dist-1)); } if(node.right != null){ q.add(new Pair(node.right, dist+1)); } } for(Map.Entry<Integer, Integer> ent : mp.entrySet()){ System.out.print(ent.getValue()+ " "); } } public static Node insert(Node root, int data) { if(root == null) { return new Node(data); } else { Node cur; if(data <= root.data) { cur = insert(root.left, data); root.left = cur; } else { cur = insert(root.right, data); root.right = cur; } return root; } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); Node root = null; while(t-- > 0) { int data = scan.nextInt(); root = insert(root, data); } scan.close(); topView(root); } }
Problem solution in C++ programming.
#include<bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
class Solution {
public:
Node* insert(Node* root, int data) {
if(root == NULL) {
return new Node(data);
} else {
Node* cur;
if(data <= root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}
/*
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
*/
void topView(Node * root) {
queue<pair<int,Node*>> q; q.push(make_pair(0,root));
map<int,Node*> ans;
for(auto i=q.front();!q.empty();q.pop(),i=q.front()){
if(!i.second) continue;
ans.insert(i);
q.push(make_pair(i.first+1,i.second->right));
q.push(make_pair(i.first-1,i.second->left));
}
for(auto i:ans) cout<<i.second->data<<" ";
}
}; //End of Solution
int main() {
Solution myTree;
Node* root = NULL;
int t;
int data;
std::cin >> t;
while(t-- > 0) {
std::cin >> data;
root = myTree.insert(root, data);
}
myTree.topView(root);
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* insert( struct node* root, int data ) {
if(root == NULL) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
} else {
struct node* cur;
if(data <= root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}
/* you only have to complete the function given below.
node is defined as
struct node {
int data;
struct node *left;
struct node *right;
};
*/
typedef struct node node;
void traverse(int *topL, int *topR, int lpos, int rpos, node *n){
if(!n) return;
if(lpos >= 0 && topL[lpos] == 0) topL[lpos] = n->data;
traverse(topL, topR, lpos + 1, rpos - 1, n->left);
traverse(topL, topR, lpos - 1, rpos + 1, n->right);
if (rpos >= 0) topR[rpos] = n->data;
}
void topView(struct node *root) {
//set up answer arrays
if(!root) return;
int left[501];
int right[501];
memset(left, 0, sizeof(int) * 501);
memset(right, 0, sizeof(int) * 501);
//traverse the tree
traverse(left, right, -1, 0, root);
//print the answer
int i = 0;
while(left[i] > 0) i++;
for(i--; i >= 0; i--) printf("%d ", left[i]);
for(i = 0; right[i] > 0; i++) printf("%d ", right[i]);
}
int main() {
struct node* root = NULL;
int t;
int data;
scanf("%d", &t);
while(t-- > 0) {
scanf("%d", &data);
root = insert(root, data);
}
topView(root);
return 0;
}
Sir, I never heard about the part inside the top view function of C++ programming. What domain should I know in C++ to understand this part?