Test: Trees - 1 - Software Development MCQ

Which of the following traversal techniques visits the left subtree, then the root, and finally the right subtree?

Which of the following operations is not typically performed on a binary search tree?

Code and Output:
#include <iostream>
using namespace std;

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

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;

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

Code and Output:
#include <iostream>
using namespace std;

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

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

   cout << root->data << " ";
   preorderTraversal(root->left);
   preorderTraversal(root->right);
}

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;

   preorderTraversal(root);
   return 0;
}
What will be the output of the above code?

Code and Output:
#include <iostream>
using namespace std;

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

Node* insert(Node* root, int key) {
   if (root == NULL) {
      Node* newNode = new Node();
      newNode->data = key;
      newNode->left = NULL;
      newNode->right = NULL;
      return newNode;
   }

   if (key < root->data)
      root->left = insert(root->left, key);
   else if (key > root->data)
      root->right = insert(root->right, key);

   return root;
}

int main() {
   Node* root = NULL;
   root = insert(root, 10);
   root = insert(root, 20);
   root = insert(root, 5);
   root = insert(root, 15);

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

Code and Output:
#include <iostream>
using namespace std;

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

int sumOfLeafNodes(Node* root) {
   if (root == NULL)
      return 0;

   if (root->left == NULL && root->right == NULL)
      return root->data;

   return sumOfLeafNodes(root->left) + sumOfLeafNodes(root->right);
}

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;

   cout << sumOfLeafNodes(root) << endl;
   return 0;
}
What will be the output of the above code?

Code and Output (HOTS):
#include <iostream>
using namespace std;

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

bool isBinarySearchTree(Node* root, int minValue, int maxValue) {
   if (root == NULL)
      return true;

   if (root->data < minValue || root->data > maxValue)
      return false;

   return isBinarySearchTree(root->left, minValue, root->data - 1) &&
          isBinarySearchTree(root->right, root->data + 1, maxValue);
}

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;

   bool isBST = isBinarySearchTree(root, INT_MIN, INT_MAX);

   cout << isBST << endl;
   return 0;
}

What will be the output of the above code?

Code and Output (HOTS):
#include <iostream>
using namespace std;

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

void printPathsToLeaf(Node* root, int path[], int pathLen) {
   if (root == NULL)
      return;

   path[pathLen] = root->data;
   pathLen++;

   if (root->left == NULL && root->right == NULL) {
      for (int i = 0; i < pathLen; i++)
         cout << path[i] << " ";
      cout << endl;
   } else {
      printPathsToLeaf(root->left, path, pathLen);
      printPathsToLeaf(root->right, path, pathLen);
   }
}

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;

   int path[100];
   printPathsToLeaf(root, path, 0);
   return 0;
}
What will be the output of the above code?

#include <iostream>
using namespace std;

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

Node* findLCA(Node* root, int n1, int n2) {
   if (root == NULL)
      return NULL;

   if (root->data == n1 || root->data == n2)
      return root;

   Node* leftLCA = findLCA(root->left, n1, n2);
   Node* rightLCA = findLCA(root->right, n1, n2);

   if (leftLCA && rightLCA)
      return root;

   return (leftLCA != NULL) ? leftLCA : rightLCA;
}

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;
   root->right->left = new Node();
   root->right->left->data = 60;
   root->right->right = new Node();
   root->right->right->data = 70;

   Node* lca = findLCA(root, 40, 70);

   cout << lca->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 convertToMirror(Node* root) {
   if (root == NULL)
      return;

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

   Node* temp = root->left;
   root->left = root->right;
   root->right = temp;
}

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;

   convertToMirror(root);

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

Which traversal technique can be used to obtain a sorted sequence of elements from a binary search tree?

Which of the following statements about binary search trees (BSTs) is correct?