Assignment: Binary Search Trees | DSA in C++ - Software Development PDF Download

Instructions

• This assignment focuses on Binary Search Trees (BST) in DSA using C++.
• The assignment includes MCQs, HOTS (Higher Order Thinking Skills) questions, Fill in the blanks, True/False statements, and Hands-On Questions.
• Each type of question has five questions, totaling 25 questions.
• The difficulty level of questions ranges from easy to hard.
• Detailed answers to all questions are provided at the end of the worksheet.

Multiple Choice Questions

(

MCQs

Q.1. Which of the following is NOT a property of a binary search tree?
(a) The left subtree of a node contains only smaller elements
(b) The right subtree of a node contains only larger elements
(c) The height of the left subtree is greater than or equal to the right subtree
(d) Each node has a unique key

Ans. (c)

Q.2. In a binary search tree, the inorder traversal of the tree will always give the keys in:
(a) Descending order
(b) Ascending order
(c) Random order
(d) None of the above

Ans. (b)

Q.3. What is the time complexity of searching for an element in a balanced binary search tree?
(a) O(n)
(b) O(log n)
(c) O(n log n)
(d) O(1)

Ans. (b)

Q.4. Which operation is used to delete a node from a binary search tree?
(a) Insertion
(b) Searching
(c) Deletion
(d) Traversal

Ans. (c)

Q.5. A binary search tree with n nodes has the maximum height when:

(a) All nodes have only left child
(b) All nodes have only right child
(c) The tree is balanced
(d) The tree is skewed to the right

Ans. (d)

HOTS (Higher Order Thinking Skills) Questions

Q.1. Write a C++ function to count the number of leaf nodes in a binary search tree.

int countLeafNodes(Node* root) {

    if (root == nullptr)

        return 0;

    if (root->left == nullptr && root->right == nullptr)

        return 1;

    return countLeafNodes(root->left) + countLeafNodes(root->right);

}

Q.2. Given a binary search tree, write a C++ function to find the node with the smallest key.

Node* findSmallestNode(Node* root) {

    if (root == nullptr || root->left == nullptr)

        return root;

    return findSmallestNode(root->left);

}

Q.3. Explain the concept of self-balancing binary search trees. Provide an example of a self-balancing binary search tree.

Self-balancing binary search trees automatically balance themselves to maintain a near-optimal height, ensuring efficient operations. An example of a self-balancing binary search tree is the AVL tree.

Q.4. Write a C++ function to check if a binary search tree is a valid binary search tree.

bool isValidBST(Node* root, int minVal, int maxVal) {

    if (root == nullptr)

        return true;

    if (root->data <= minVal || root->data >= maxVal)

        return false;

    return isValidBST(root->left, minVal, root->data) && isValidBST(root->right, root->data, maxVal);

}

Q.5. Given a binary search tree, write a C++ function to find the height of the tree.

int getHeight(Node* root) {

    if (root == nullptr)

        return 0;

    int leftHeight = getHeight(root->left);

    int rightHeight = getHeight(root->right);

    return 1 + max(leftHeight, rightHeight);

}

Fill in the blanks

1. In a binary search tree, the _______ subtree of a node contains elements greater than the node's key.

In a binary search tree, the right subtree of a node contains elements greater than the node's key.

2. The _______ of a binary search tree is determined by the maximum number of edges from the root to a leaf.

The height of a binary search tree is determined by the maximum number of edges from the root to a leaf.

3. In a binary search tree, the _______ subtree of a node contains elements smaller than the node's key.

In a binary search tree, the left subtree of a node contains elements smaller than the node's key.

4.  The _______ property of a binary search tree states that each node has a unique key.

The unique key property of a binary search tree states that each node has a unique key.

5. In a binary search tree, the _______ traversal visits the left subtree, then the root, and finally the right subtree.

In a binary search tree, the inorder traversal visits the left subtree, then the root, and finally the right subtree.

True/False Statements

1. In a binary search tree, the maximum element is always found at the root node.

False

2. The time complexity of searching for an element in an unbalanced binary search tree is O(n).

True

3. A binary search tree can have duplicate keys.

True

4. The height of a binary search tree is always equal to the number of nodes in the tree.

False

5. In a binary search tree, the left child of a node always has a smaller key than the parent node.

True

Hands-On Questions

Q.1. Implement a C++ class for a binary search tree that supports insertion, deletion, and searching of nodes.

class Node {

public:

    int data;

    Node* left;

    Node* right;

    Node(int value) {

        data = value;

        left = nullptr;

        right = nullptr;

    }

};

class BinarySearchTree {

private:

    Node* root;

public:

    BinarySearchTree() {

        root = nullptr;

    }

    void insert(int value) {

        // Implementation of insertion

    }

    bool search(int value) {

        // Implementation of search

    }

    void remove(int value) {

        // Implementation of deletion

    }

};

Q.2. Given the following keys, build a binary search tree:
Keys: 5, 2, 8, 1, 4, 6, 9, 3, 7

The binary search tree:

            5

          /   \

        2       8

       / \     / \

      1   4   6   9

         /       /

        3       7

Q.3. Perform an inorder traversal of the binary search tree built in question 2.

Inorder traversal of the binary search tree: 1, 2, 3, 4, 5, 6, 7, 8, 9

Q.4. Write a C++ function to find the maximum element in a binary search tree.

int findMax(Node* root) {

    if (root == nullptr)

        return INT_MIN;

    if (root->right == nullptr)

        return root->data;

    return findMax(root->right);

}

Q.5. Write a C++ function to delete a node with a specific key from a binary search tree.

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 = findSmallestNode(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}