Test: Trees - 2 - Software Development MCQ

#include <iostream>
using namespace std;

struct Node {
   int data;
   Node* left;
   Node* right;
};

Node* findMin(Node* root) {
   if (root == NULL)
      return NULL;

   if (root->left == NULL)
      return root;

   return findMin(root->left);
}

int main() {
   Node* root = new Node();
   root->data = 10;
   root->left = new Node();
   root->left->data = 5;
   root->right = new Node();
   root->right->data = 15;
   root->right->left = new Node();
   root->right->left->data = 12;
   root->right->right = new Node();
   root->right->right->data = 18;

   Node* minNode = findMin(root);

   cout << minNode->data << endl;
   return 0;
}
What will be the output of the above code?

#include <iostream>
using namespace std;

struct Node {
   int data;
   Node* left;
   Node* right;
};

void deleteTree(Node* root) {
   if (root == NULL)
      return;

   deleteTree(root->left);
   deleteTree(root->right);

   delete root;
}

int main() {
   Node* root = new Node();
   root->data = 10;
   root->left = new Node();
   root->left->data = 20;
   root->right = new Node();
   root->right->data = 30;
   root->left->left = new Node();
   root->left->left->data = 40;
   root->left->right = new Node();
   root->left->right->data = 50;

   deleteTree(root);

   cout << root->data << endl;
   return 0;
}
What will be the output of the above code?

What is a tree data structure?

Which traversal technique visits the root node first?

Which traversal technique visits the left subtree first?

In a binary search tree, which property holds true for any node?

What is the time complexity of searching for an element in a binary search tree?

What will be the output of the following code?
#include <iostream>

struct Node {
   int data;
   Node* left;
   Node* right;
};

Node* createNode(int data) {
   Node* newNode = new Node();
   newNode->data = data;
   newNode->left = nullptr;
   newNode->right = nullptr;

   return newNode;
}

void insertNode(Node* root, int data) {
   if (root->data > data) {
      if (root->left == nullptr) {
         root->left = createNode(data);
      } else {
         insertNode(root->left, data);
      }
   } else {
      if (root->right == nullptr) {
         root->right = createNode(data);
      } else {
         insertNode(root->right, data);
      }
   }
}

void inOrderTraversal(Node* node) {
   if (node == nullptr)
      return;

   inOrderTraversal(node->left);
   std::cout << node->data << " ";
   inOrderTraversal(node->right);
}

int main() {
   Node* root = createNode(10);
   insertNode(root, 20);
   insertNode(root, 30);

   inOrderTraversal(root);

   delete root->left;
   delete root->right;
   delete root;

   return 0;
}

What will be the output of the following code?
#include <iostream>

struct Node {
   int data;
   Node* left;
   Node* right;
};

Node* deleteNode(Node* root, int key) {
   if (root == nullptr)
      return root;

   if (key < root->data) {
      root->left = deleteNode(root->left, key);
   } else if (key > root->data) {
      root->right = deleteNode(root->right, key);
   } else {
      if (root->left == nullptr) {
         Node* temp = root->right;
         delete root;
         return temp;
      } else if (root->right == nullptr) {
         Node* temp = root->left;
         delete root;
         return temp;
      }

      Node* temp = root->right;
      while (temp->left != nullptr) {
         temp = temp->left;
      }
      root->data = temp->data;
      root->right = deleteNode(root->right, temp->data);
   }

   return root;
}

void inOrderTraversal(Node* node) {
   if (node == nullptr)
      return;

   inOrderTraversal(node->left);
   std::cout << node->data << " ";
   inOrderTraversal(node->right);
}

int main() {
   Node* root = new Node();
   root->data = 10;
   root->left = new Node();
   root->right = new Node();
   root->left->data = 20;
   root->right->data = 30;

   root = deleteNode(root, 20);

   inOrderTraversal(root);

   delete root->left;
   delete root->right;
   delete root;

   return 0;
}

Which traversal technique is used in the following code?
#include <iostream>

struct Node {
   int data;
   Node* left;
   Node* right;
};

void preOrderTraversal(Node* node) {
   if (node == nullptr)
      return;

   std::cout << node->data << " ";
   preOrderTraversal(node->left);
   preOrderTraversal(node->right);
}

int main() {
   Node* root = new Node();
   root->data = 10;
   root->left = new Node();
   root->right = new Node();
   root->left->data = 20;
   root->right->data = 30;

   preOrderTraversal(root);

   delete root->left;
   delete root->right;
   delete root;

   return 0;
}

What will be the output of the following code?
#include <iostream>

struct Node {
   int data;
   Node* left;
   Node* right;
};

int findMin(Node* root) {
   if (root == nullptr)
      return INT_MAX;

   int minVal = root->data;
   int leftMin = findMin(root->left);
   int rightMin = findMin(root->right);

   if (leftMin < minVal)
      minVal = leftMin;
   if (rightMin < minVal)
      minVal = rightMin;

   return minVal;
}

int main() {
   Node* root = new Node();
   root->data = 10;
   root->left = new Node();
   root->right = new Node();
   root->left->data = 20;
   root->right->data = 30;

   int minValue = findMin(root);

   delete root->left;
   delete root->right;
   delete root;

   std::cout << minValue;

   return 0;
}

What will be the output of the following code?
#include <iostream>

struct Node {
   int data;
   Node* left;
   Node* right;
};

bool searchNode(Node* root, int key) {
   if (root == nullptr)
      return false;

   if (root->data == key)
      return true;
   else if (key < root->data)
      return searchNode(root->left, key);
   else
      return searchNode(root->right, key);
}

int main() {
   Node* root = new Node();
   root->data = 10;
   root->left = new Node();
   root->right = new Node();
   root->left->data = 20;
   root->right->data = 30;

   bool isFound = searchNode(root, 20);

   delete root->left;
   delete root->right;
   delete root;

   std::cout << std::boolalpha << isFound;

   return 0;
}