Algorithm


Problem Name: Data Structures - Tree : Top View

Problem Link: https://www.hackerrank.com/challenges/tree-top-view/problem?isFullScreen=true

In this HackerRank in Data Structures - Tree : Top View solutions

Given a pointer to the root of a binary tree, print the top view of the binary tree.

 

The tree as seen from the top the nodes, is called the top view of the tree.

 

For example :

 

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4

Top View : 1- > 2- > 5- > 6

Complete the function topView and print the resulting values on a single line separated by space.

Input Format

You are given a function,

void topView(node * root) {

}

Constraints

1 <= Nodes in the tree <= 500

Output Format

Print the values on a single line separated by space.

Sample Input

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4

Sample Output

1 2 5 6

Explanation

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
From the top, only nodes 1,2,5,6 are visible.

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - 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;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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 q = new LinkedList();
        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);
    }   
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - 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)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Tree: Height of a Binary Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Tree : Tree: Level Order Traversal solution in Hackerrank - Hacerrank solution C, C++, java,js, Python