SHARE
TWEET

Untitled

a guest Nov 17th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. struct Node {
  3.     int data;
  4.     Node* left = nullptr;
  5.     Node* right = nullptr;
  6.     Node(int value) {
  7.         data = value;
  8.     }
  9. };
  10.  
  11. class BST {
  12. private:
  13.     Node* root = nullptr;
  14.  
  15.  
  16.     Node* addNode(int value, Node* current) {
  17.         if (!current) {
  18.             return new Node(value);
  19.         }
  20.  
  21.         if (value < current->data) {
  22.             current->left = addNode(value, current->left);
  23.         }
  24.         else if (value > current->data) {
  25.             current->right = addNode(value, current->right);
  26.         }
  27.  
  28.         return current;
  29.     }
  30.     void _inorder(Node* current) const {
  31.         if (current) {
  32.             _inorder(current->left);
  33.             std::cout << current->data << " ";
  34.             _inorder(current->right);
  35.         }
  36.     }
  37.  
  38. public:
  39.     void insert(int value) {
  40.         root = addNode(value, root);
  41.     }
  42.  
  43.     void inorder() const {
  44.         _inorder(root);
  45.         std::cout << "\n";
  46.     }
  47. };
  48.  
  49. int findDistance(Node *root, int x)
  50. {
  51.     if (root == NULL)
  52.         return -1;
  53.  
  54.     int dist = -1;
  55.  
  56.     if ((root->data == x) ||
  57.         (dist = findDistance(root->left, x)) >= 0 ||
  58.         (dist = findDistance(root->right, x)) >= 0)
  59.         return dist + 1;
  60.  
  61.     return dist;
  62. }
  63. int main()
  64. {
  65.     BST s;
  66.     int nodes = 0;
  67.     int findNode = 0;
  68.     int N = 0;
  69.     std::cin >> N;
  70.     int K = 0;
  71.     std::cin >> K;
  72.  
  73.     for (int i = 0; i < N; i++) {
  74.         std::cin >> nodes;
  75.         s.insert(nodes);
  76.     }
  77.  
  78.     for (int i = 0; i < K; i++)
  79.     {
  80.         std::cin >> findNode;
  81.     }
  82.     for (int i = 0; i < K; i++)
  83.     {
  84.         std::cout << findDistance(, findNode) << std::endl;
  85.     }
  86.  
  87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top