fork download
copy 
  1. // { Driver Code Starts
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define MAX_HEIGHT 100000
  5.  
  6. // Tree Node
  7. struct Node
  8. {
  9.     int data;
  10.     Node* left;
  11.     Node* right;
  12. };
  13.  
  14. // Utility function to create a new Tree Node
  15. Node* newNode(int val)
  16. {
  17.     Node* temp = new Node;
  18.     temp->data = val;
  19.     temp->left = NULL;
  20.     temp->right = NULL;
  21.  
  22.     return temp;
  23. }
  24.  
  25.  
  26. vector <int> bottomView(Node *root);
  27.  
  28. // Function to Build Tree
  29. Node* buildTree(string str)
  30. {
  31.     // Corner Case
  32.     if(str.length() == 0 || str[0] == 'N')
  33.         return NULL;
  34.  
  35.     // Creating vector of strings from input
  36.     // string after spliting by space
  37.     vector<string> ip;
  38.  
  39.     istringstream iss(str);
  40.     for(string str; iss >> str; )
  41.         ip.push_back(str);
  42.  
  43.     // Create the root of the tree
  44.     Node* root = newNode(stoi(ip[0]));
  45.  
  46.     // Push the root to the queue
  47.     queue<Node*> queue;
  48.     queue.push(root);
  49.  
  50.     // Starting from the second element
  51.     int i = 1;
  52.     while(!queue.empty() && i < ip.size()) {
  53.  
  54.         // Get and remove the front of the queue
  55.         Node* currNode = queue.front();
  56.         queue.pop();
  57.  
  58.         // Get the current node's value from the string
  59.         string currVal = ip[i];
  60.  
  61.         // If the left child is not null
  62.         if(currVal != "N") {
  63.  
  64.             // Create the left child for the current node
  65.             currNode->left = newNode(stoi(currVal));
  66.  
  67.             // Push it to the queue
  68.             queue.push(currNode->left);
  69.         }
  70.  
  71.         // For the right child
  72.         i++;
  73.         if(i >= ip.size())
  74.             break;
  75.         currVal = ip[i];
  76.  
  77.         // If the right child is not null
  78.         if(currVal != "N") {
  79.  
  80.             // Create the right child for the current node
  81.             currNode->right = newNode(stoi(currVal));
  82.  
  83.             // Push it to the queue
  84.             queue.push(currNode->right);
  85.         }
  86.         i++;
  87.     }
  88.  
  89.     return root;
  90. }
  91.  
  92.  
  93.  
  94. int main() {
  95.     int t;
  96.     string tc;
  97.     getline(cin, tc);
  98.     t=stoi(tc);
  99.     while(t--)
  100.     {
  101.         string s ,ch;
  102.         getline(cin, s);
  103.         Node* root = buildTree(s);
  104.  
  105.         vector <int> res = bottomView(root);
  106.         for (int i : res) cout << i << " ";
  107.         cout << endl;
  108.     }
  109.     return 0;
  110. }
  111.  
  112.  
  113. // } Driver Code Ends
  114.  
  115.  
  116. /* Tree node class
  117.  
  118. struct Node
  119. {
  120.     int data; //data of the node
  121.     Node *left, *right; //left and right references
  122.  
  123.     // Constructor of tree node
  124.     Node(int key)
  125.     {
  126.         data = key;
  127.         left = right = NULL;
  128.     }
  129. }; */
  130.  
  131. // Method that returns the bottom view.
  132.  
  133. #include<map>
  134.  
  135. vector <int> bottomView(Node *root)
  136. {
  137.    queue<pair<Node*,int>> q;
  138.    map <int, int> m;
  139.    map <int, int> ::iterator i;
  140.  
  141.    vector<int> v;
  142.  
  143.    int n=0, x_dist=0;
  144.    Node *x;
  145.  
  146.  
  147. if(!root)
  148.     return v;
  149.  
  150.  
  151.  q.push({root,0});
  152.  
  153.    while(!q.empty())
  154.    {
  155.        n = q.size();
  156.  
  157.        while(n--)
  158.        {
  159.            x = q.front().first;
  160.            x_dist = q.front().second;
  161.  
  162.            if(m.find(x_dist)!= m.end())
  163.             m[x_dist] = x->data;
  164.  
  165.  
  166.             else
  167.                 { m.insert({x_dist, x->data}); }
  168.  
  169.            if(x->left)q.push({x->left, x_dist-1});
  170.            if(x->right)q.push({x->right,x_dist+1});    
  171.  
  172.  
  173.            q.pop();
  174.        }
  175.    }
  176.  
  177.     for(i= m.begin(); i!=m.end(); i++)
  178.     {
  179.         v.push_back(i->second);
  180.     }
  181.  
  182.    return v;
  183. }
  184.  
Success #stdin #stdout 0s 4416KB
comments (?)
stdin
copy 
14 14 3 N 8 8 12 N 6 17 3 N 1 11 10 N 6 6 13 N 10 17 7 N 11 7
stdout
copy
https://ideone.com/9Mg6Kr
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!