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

Instructions

Answer the following questions based on your understanding of Binary Trees in DSA using C++. Choose the correct option in MCQs, fill in the blanks with appropriate answers, determine the truth value of True/False statements, and solve the hands-on questions.

Multiple Choice Questions (MCQs)

Q.1. In a binary tree, each node can have a maximum of ______ children.
(a) 0
(b) 1
(c) 2
(d) 3

Ans. (c)

Q.2. Which of the following statements about binary trees is FALSE?
(a) Binary trees can be empty.
(b) Binary trees can have only one node.
(c) Binary trees can have a maximum of two children per node.
(d) Binary trees can have an arbitrary number of children per node.

Ans. (d)

Q.3. In a binary tree, the number of leaf nodes is equal to the number of nodes with ______ child(ren).(a) 0
(b) 1
(c) 2
(d) 3

Ans. (a)

Q.4. The height of a binary tree with 'n' nodes is at most ______.
(a) log(n)
(b) n
(c) n + 1
(d) 2^n

Ans. (b)

Q.5. Which traversal technique visits the left subtree, then the root, and finally the right subtree?
(a) Preorder traversal
(b) Inorder traversal
(c) Postorder traversal
(d) Level order traversal

Ans. (b)

HOTS (Higher Order Thinking Skills) Questions

Q.1. Write a recursive function in C++ to count the number of leaf nodes in a binary 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. Implement a non-recursive (iterative) function in C++ to calculate the height of a binary tree.

int calculateHeight(Node* root) {

    if (root == nullptr)

        return 0;

    queue<Node*> q;

    q.push(root);

    int height = 0;

    while (!q.empty()) {

        int size = q.size();

        while (size > 0) {

            Node* current = q.front();

            q.pop();

            if (current->left)

                q.push(current->left);

            if (current->right)

                q.push(current->right);

            size--;

        }

        height++;

    }

    return height;

}

Q.3. Explain the concept of a perfect binary tree and provide an example.

A perfect binary tree is a binary tree in which all levels are completely filled, except possibly the last level, which is filled from left to right. For example:

    1

  /   \

 2     3

/ \   / \

4 5 6 7

Q.4. Write a C++ function to check whether a binary tree is a binary search tree (BST) or not.

bool isBSTUtil(Node* node, int min, int max) {

    if (node == nullptr)

        return true;

    if (node->data < min || node->data > max)

        return false;

    return isBSTUtil(node->left, min, node->data - 1) && isBSTUtil(node->right, node->data + 1, max);

}

bool isBST(Node* root) {

    return isBSTUtil(root, INT_MIN, INT_MAX);

}

Q.5. Discuss the difference between a binary tree and a binary search tree.

In a binary tree, each node can have at most two children, while in a binary search tree (BST), for each node, all elements in its left subtree are smaller, and all elements in its right subtree are larger. Therefore, all BSTs are binary trees, but not all binary trees are BSTs.

Fill in the Blanks:
1. In a binary tree, each node can have ______ children.

In a binary tree, each node can have at most two children.

2. The maximum number of nodes at level 'd' in a binary tree is ______.

The maximum number of nodes at level 'd' in a binary tree is 2^d.

3. A node is called ______ if it does not have any children.

A node is called leaf node if it does not have any children.

4. The ______ of a binary tree is the number of edges on the longest path from the root to a leaf node.

The height of a binary tree is the number of edges on the longest path from the root to a leaf node.

5. A binary tree is called ______ if all its levels are completely filled except possibly the last level, which is filled from left to right.

A binary tree is called a complete binary tree if all its levels are completely filled except possibly the last level, which is filled from left to right.

True/False

1. In a binary tree, the left child is always smaller than the right child in a binary search tree.

False

2. The time complexity of searching for a key in a binary search tree is O(n).

False

3. A binary search tree can have duplicate values.

True

4. All binary trees are binary search trees.

False

5. The height of a binary tree can be equal to the number of nodes in the tree.

True

Hands-On Questions

Q.1. Implement a C++ program to create a binary tree and perform inorder traversal.

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* left;

    Node* right;

};

Node* createNode(int value) {

    Node* newNode = new Node();

    if (!newNode) {

        cout << "Memory error\n";

        return nullptr;

    }

    newNode->data = value;

    newNode->left = nullptr;

    newNode->right = nullptr;

    return newNode;

}

Node* insertNode(Node* root, int data) {

    if (root == nullptr) {

        root = createNode(data);

        return root;

    }

    queue<Node*> q;

    q.push(root);

    while (!q.empty()) {

        Node* temp = q.front();

        q.pop();

        if (temp->left != nullptr)

            q.push(temp->left);

        else {

            temp->left = createNode(data);

            return root;

        }

        if (temp->right != nullptr)

            q.push(temp->right);

        else {

            temp->right = createNode(data);

            return root;

        }

    }

    return root;

}

void inorderTraversal(Node* root) {

    if (root == nullptr)

        return;

    inorderTraversal(root->left);

    cout << root->data << " ";

    inorderTraversal(root->right);

}

int main() {

    Node* root = createNode(1);

    insertNode(root, 2);

    insertNode(root, 3);

    insertNode(root, 4);

    insertNode(root, 5);

    cout << "Inorder Traversal: ";

    inorderTraversal(root);

    return 0;

}

Q.2. Write a C++ program to find the maximum element in a binary tree.

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* left;

    Node* right;

};

Node* createNode(int value) {

    Node* newNode = new Node();

    if (!newNode) {

        cout << "Memory error\n";

        return nullptr;

    }

    newNode->data = value;

    newNode->left = nullptr;

    newNode->right = nullptr;

    return newNode;

}

int findMaxElement(Node* root) {

    if (root == nullptr)

        return INT_MIN;

    int maxVal = root->data;

    int leftMax = findMaxElement(root->left);

    int rightMax = findMaxElement(root->right);

    if (leftMax > maxVal)

        maxVal = leftMax;

    if (rightMax > maxVal)

        maxVal = rightMax;

    return maxVal;

}

int main() {

    Node* root = createNode(1);

    root->left = createNode(2);

    root->right = createNode(3);

    root->left->left = createNode(4);

    root->left->right = createNode(5);

    int maxElement = findMaxElement(root);

    cout << "Maximum element in the binary tree: " << maxElement;

    return 0;

}

Q.3. Implement a C++ program to count the total number of nodes in a binary tree.

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* left;

    Node* right;

};

Node* createNode(int value) {

    Node* newNode = new Node();

    if (!newNode) {

        cout << "Memory error\n";

        return nullptr;

    }

    newNode->data = value;

    newNode->left = nullptr;

    newNode->right = nullptr;

    return newNode;

}

int countNodes(Node* root) {

    if (root == nullptr)

        return 0;

    return 1 + countNodes(root->left) + countNodes(root->right);

}

int main() {

    Node* root = createNode(1);

    root->left = createNode(2);

    root->right = createNode(3);

    root->left->left = createNode(4);

    root->left->right = createNode(5);

    int totalNodes = countNodes(root);

    cout << "Total number of nodes in the binary tree: " << totalNodes;

    return 0;

}

Q.4. Write a C++ program to calculate the diameter of a binary tree.

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* left;

    Node* right;

};

Node* createNode(int value) {

    Node* newNode = new Node();

    if (!newNode) {

        cout << "Memory error\n";

        return nullptr;

    }

    newNode->data = value;

    newNode->left = nullptr;

    newNode->right = nullptr;

    return newNode;

}

int height(Node* root) {

    if (root == nullptr)

        return 0;

    int leftHeight = height(root->left);

    int rightHeight = height(root->right);

    return max(leftHeight, rightHeight) + 1;

}

int diameter(Node* root) {

    if (root == nullptr)

        return 0;

    int leftHeight = height(root->left);

    int rightHeight = height(root->right);

    int leftDiameter = diameter(root->left);

    int rightDiameter = diameter(root->right);

    return max(leftHeight + rightHeight + 1, max(leftDiameter, rightDiameter));

}

int main() {

    Node* root = createNode(1);

    root->left = createNode(2);

    root->right = createNode(3);

    root->left->left = createNode(4);

    root->left->right = createNode(5);

    int treeDiameter = diameter(root);

    cout << "Diameter of the binary tree: " << treeDiameter;

    return 0;

}

Q.5. Implement a C++ program to delete a given node from a binary tree.

#include <iostream>

using namespace std;

struct Node {

    int data;

    Node* left;

    Node* right;

};

Node* createNode(int value) {

    Node* newNode = new Node();

    if (!newNode) {

        cout << "Memory error\n";

        return nullptr;

    }

    newNode->data = value;

    newNode->left = nullptr;

    newNode->right = nullptr;

    return newNode;

}

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* current = root->right;

        while (current->left != nullptr)

            current = current->left;

        root->data = current->data;

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

    }

    return root;

}

void inorderTraversal(Node* root) {

    if (root == nullptr)

        return;

    inorderTraversal(root->left);

    cout << root->data << " ";

    inorderTraversal(root->right);

}

int main() {

    Node* root = createNode(5);

    root->left = createNode(3);

    root->right = createNode(7);

    root->left->left = createNode(2);

    root->left->right = createNode(4);

    root->right->left = createNode(6);

    root->right->right = createNode(8);

    cout << "Before deletion, inorder traversal: ";

    inorderTraversal(root);

    int key = 7;

    root = deleteNode(root, key);

    cout << "\nAfter deletion of key " << key << ", inorder traversal: ";

    inorderTraversal(root);

   return 0;

}