fork download
copy 
  1.  
  2. // C++ Program to print Bottom View of Binary Tree
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // Tree node class
  6. struct Node
  7. {
  8.     int data; //data of the node
  9.     Node *left, *right; //left and right references
  10.     // Constructor of tree node
  11.     Node(int key)
  12.     {
  13.         data = key;
  14.         left = right = NULL;
  15.     }
  16. };
  17. // Method that prints the bottom view.
  18. void bottomView(Node *root);
  19. /* Driver program to test size function*/
  20. int main()
  21. {
  22.   int t;
  23.   struct Node *child;
  24.   scanf("%d", &t);
  25.   while (t--)
  26.   {
  27.      map<int, Node*> m;
  28.      int n;
  29.      scanf("%d",&n);
  30.      struct Node *root = NULL;
  31.      while (n--)
  32.      {
  33.         Node *parent;
  34.         char lr;
  35.         int n1, n2;
  36.         scanf("%d %d %c", &n1, &n2, &lr);
  37.         if (m.find(n1) == m.end())
  38.         {
  39.            parent = new Node(n1);
  40.            m[n1] = parent;
  41.            if (root == NULL)
  42.              root = parent;
  43.         }
  44.         else
  45.            parent = m[n1];
  46.         child = new Node(n2);
  47.         if (lr == 'L')
  48.           parent->left = child;
  49.         else
  50.           parent->right = child;
  51.         m[n2]  = child;
  52.      }
  53.      bottomView(root);
  54.      cout << endl;
  55.   }
  56.   return 0;
  57. }
  58.  
  59. /*This is a function problem.You only need to complete the function given below*/
  60. /* Tree node class
  61. struct Node
  62. {
  63.     int data; //data of the node
  64.     Node *left, *right; //left and right references
  65.     // Constructor of tree node
  66.     Node(int key)
  67.     {
  68.         data = key;
  69.         left = right = NULL;
  70.     }
  71. }; */
  72. // Method that prints the bottom view.
  73. map<int,int>mp;
  74. void dfs(Node* root,int d)
  75. {
  76.     if(root==NULL){return;}
  77.     mp[d]=root->data;
  78.     dfs(root->left,d-1);
  79.     dfs(root->right,d+1);
  80.     return;
  81. }
  82. void bottomView(Node *root)
  83. {
  84.     mp.clear();
  85.     dfs(root,0);
  86.     map<int, int>::iterator itr;
  87.     for(itr=mp.begin();itr!=mp.end();itr++)
  88.     {
  89.         cout<<itr->second<<" ";
  90.     }
  91. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
2
2
1 2 R 1 3 L
4
10 20 L 10 30 R 20 40 L 20 60 R
stdout
copy 
3 1 2 
40 20 60 30
https://ideone.com/FhtHfl
language:
C++14 (gcc 8.3)
created:
4 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!