Chapter 1. Question Bank 2.

Chapter 1. Questions and Answers ( long answer)

1. Apply heap sort to sort the given list: {10, 30, 50, 20, 60, 40}.

Answer: A)  Note : You can also write Answer B) if the question is for 3 marks.

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It involves two main steps:

  1. Build a Max Heap: Convert the given list into a max heap (parent node is greater than its children).

  2. Sort the Heap: Repeatedly extract the maximum element from the heap and place it at the end of the list.

Given List: {10, 30, 50, 20, 60, 40}
Step 1: Build a Max Heap

  1. Start with the given list:
    [10, 30, 50, 20, 60, 40]
    Represented as a binary tree:

     
          10
    /    \
  30      50
 /  \    /
20  60 40

  2. Convert the tree into a max heap:

    • Start from the last non-leaf node (index = 2, value = 50).

    • Heapify the subtree rooted at 50: No change needed.

    • Move to index = 1 (value = 30): Swap 30 and 60.

    • Move to index = 0 (value = 10): Swap 10 and 60, then swap 10 and 30.

    Max Heap:

     
          60
    /    \
  30      50
 /  \    /
20  10 40

    Array representation: [60, 30, 50, 20, 10, 40]

Step 2: Sort the Heap

  1. Swap the root (60) with the last element (40):
    [40, 30, 50, 20, 10, 60]
    Heapify the remaining list:

     
          50
    /    \
  30      40
 /  \
20  10

    Array: [50, 30, 40, 20, 10, 60]

  2. Swap the root (50) with the last element (10):
    [10, 30, 40, 20, 50, 60]
    Heapify the remaining list:

     
          40
    /    \
  30      10
 /
20

    Array: [40, 30, 10, 20, 50, 60]

  3. Swap the root (40) with the last element (20):
    [20, 30, 10, 40, 50, 60]
    Heapify the remaining list:

     
          30
    /    \
  20      10

    Array: [30, 20, 10, 40, 50, 60]

  4. Swap the root (30) with the last element (10):
    [10, 20, 30, 40, 50, 60]
    Heapify the remaining list:

     
          20
    /
  10

    Array: [20, 10, 30, 40, 50, 60]

  5. Swap the root (20) with the last element (10):
    [10, 20, 30, 40, 50, 60]
    Heapify the remaining list:

     
          10

    Array: [10, 20, 30, 40, 50, 60]

Final Sorted List:

[10, 20, 30, 40, 50, 60]

Answer B) ( For 3 marks) 
Given List: {10, 30, 50, 20, 60, 40}
Step 1: Build Max Heap

  1. Convert the list into a max heap:

     
          60
    /    \
  30      50
 /  \    /
20  10 40

    Array: [60, 30, 50, 20, 10, 40]

Step 2: Sort the Heap

  1. Repeatedly extract the max element and heapify:

    • Swap 60 (root) with 40 (last element), heapify.

    • Swap 50 with 10, heapify.

    • Swap 40 with 20, heapify.

    • Swap 30 with 10, heapify.

    • Swap 20 with 10, heapify.

Final Sorted List:

[10, 20, 30, 40, 50, 60]

2. Apply Huffman encoding to the string “DATA” using frequency counts: D=5, A=3, T=2.

To solve the problem of applying Huffman encoding to the string “DATA” using the frequency counts (D=5, A=3, T=2), we will follow the Huffman algorithm  

  1. Input: A set of characters and their frequencies.

  2. Output: A Huffman tree and the corresponding Huffman codes for each character.

Step 1: Initialize a Min-Heap

  • Create a min-heap (priority queue) where each node represents a character and its frequency.

  • Insert all the characters into the min-heap based on their frequencies.

For the given input:

Characters: D (5), A (3), T (2)

The min-heap is initialized as:

[T (2), A (3), D (5)]
Step 2: Build the Huffman Tree

  • While the min-heap has more than one node:

    1. Extract the two nodes with the smallest frequencies. Let these be x and y.

    2. Create a new node z such that:

      • The frequency of z is the sum of the frequencies of x and y.

      • x is the left child of z.

      • y is the right child of z.

    3. Insert z into the min-heap.

Iteration 1:

  • Extract T (2) and A (3).

  • Create a new node z with frequency 2 + 3 = 5.

  • Insert z into the min-heap.

Updated min-heap:

[z (5), D (5)]
Iteration 2:

  • Extract z (5) and D (5).

  • Create a new node w with frequency 5 + 5 = 10.

  • Insert w into the min-heap.

Updated min-heap:

[w (10)]

Now the min-heap has only one node, so the Huffman tree is complete.

Step 3: Construct the Huffman Tree

The final Huffman tree is:

          w (10)
         /      \
     z (5)      D (5)
    /     \
T (2)    A (3)
Step 4: Assign Huffman Codes

  • Traverse the Huffman tree from the root to each leaf node.

  • Assign 0 for left branches and 1 for right branches.

Codes:

  • D: Path = 0 → Code = 0

  • T: Path = 1 → 0 → Code = 10

  • A: Path = 1 → 1 → Code = 11

Step 5: Encode the String “DATA”

Using the Huffman codes:

  • D = 0

  • A = 11

  • T = 10

The encoded string for “DATA” is:

D  A  T  A
0 11 10 11

Combined: 0111011

3. Apply the greedy strategy to construct an optimal Huffman tree for the characters {a, b, c, d} with frequencies {4, 8, 6, 12}.

Answer A) :

To construct an optimal Huffman tree for the characters {a, b, c, d} with frequencies {4, 8, 6, 12} using the greedy strategy, we follow the Huffman algorithm 

Step 1: Initialize a Min-Heap

  • Create a min-heap (priority queue) where each node represents a character and its frequency.

  • Insert all the characters into the min-heap based on their frequencies.

For the given input:

Characters: a (4), b (8), c (6), d (12)

The min-heap is initialized as:

[a (4), c (6), b (8), d (12)]
Step 2: Build the Huffman Tree

  • While the min-heap has more than one node:

    1. Extract the two nodes with the smallest frequencies. Let these be x and y.

    2. Create a new node z such that:

      • The frequency of z is the sum of the frequencies of x and y.

      • x is the left child of z.

      • y is the right child of z.

    3. Insert z into the min-heap.

Iteration 1:

  • Extract a (4) and c (6).

  • Create a new node z1 with frequency 4 + 6 = 10.

  • Insert z1 into the min-heap.

Updated min-heap:

[b (8), z1 (10), d (12)]
Iteration 2:

  • Extract b (8) and z1 (10).

  • Create a new node z2 with frequency 8 + 10 = 18.

  • Insert z2 into the min-heap.

Updated min-heap:

[d (12), z2 (18)]
Iteration 3:

  • Extract d (12) and z2 (18).

  • Create a new node z3 with frequency 12 + 18 = 30.

  • Insert z3 into the min-heap.

Updated min-heap:

[z3 (30)]

Now the min-heap has only one node, so the Huffman tree is complete.

Step 3: Construct the Huffman Tree

The final Huffman tree is:

          z3 (30)
         /      \
     d (12)    z2 (18)
              /      \
          b (8)     z1 (10)
                   /      \
               a (4)     c (6)
Step 4: Assign Huffman Codes

  • Traverse the Huffman tree from the root to each leaf node.

  • Assign 0 for left branches and 1 for right branches.

  • d: Path = 0 → Code = 0

  • b: Path = 1 → 0 → Code = 10

  • a: Path = 1 → 1 → 0 → Code = 110

  • c: Path = 1 → 1 → 1 → Code = 111

 

Short Answer B : 

To construct an optimal Huffman tree for characters {a, b, c, d} with frequencies {4, 8, 6, 12} using the greedy strategy, follow these steps:

  1. Initialize a Min-Heap:

    • Insert all characters with their frequencies into a min-heap:

       
      [a (4), c (6), b (8), d (12)]
  2. Build the Huffman Tree:

    • Repeatedly combine the two nodes with the smallest frequencies:

      • Combine a (4) and c (6) → z1 (10).

      • Combine b (8) and z1 (10) → z2 (18).

      • Combine d (12) and z2 (18) → z3 (30).

  3. Final Huffman Tree:
     
           z3 (30)
      /      \
  d (12)    z2 (18)
           /      \
       b (8)     z1 (10)
                /      \
            a (4)     c (6)
  4. Assign Huffman Codes:

    • Traverse the tree and assign codes:

      • d = 0, b = 10, a = 110, c = 111.

4. Show the step-by-step process of inserting elements into a BST.

Answer  :
Key Properties of BST:

  1. Left Subtree: All nodes in the left subtree of a node have values less than the node’s value.

  2. Right Subtree: All nodes in the right subtree of a node have values greater than the node’s value.

  3. No Duplicates: BSTs typically do not allow duplicate values.

To show the step-by-step process of inserting elements into a Binary Search Tree (BST), we will use the following sequence of elements: [50, 30, 70, 20, 40, 60, 80].

Step 1: Insert 50

  • The tree is empty, so 50 becomes the root node.

 
    50
Step 2: Insert 30

  • Compare 30 with the root node 50.

  • Since 30 < 50, it is inserted as the left child of 50.

 
      50
     /
   30
Step 3: Insert 70

  • Compare 70 with the root node 50.

  • Since 70 > 50, it is inserted as the right child of 50.

 
      50
     /  \
   30    70
Step 4: Insert 20

  • Compare 20 with the root node 50.

  • Since 20 < 50, move to the left subtree (30).

  • Compare 20 with 30.

  • Since 20 < 30, it is inserted as the left child of 30.

 
      50
     /  \
   30    70
  /
20
Step 5: Insert 40

  • Compare 40 with the root node 50.

  • Since 40 < 50, move to the left subtree (30).

  • Compare 40 with 30.

  • Since 40 > 30, it is inserted as the right child of 30.

 
      50
     /  \
   30    70
  /  \
20   40
Step 6: Insert 60

  • Compare 60 with the root node 50.

  • Since 60 > 50, move to the right subtree (70).

  • Compare 60 with 70.

  • Since 60 < 70, it is inserted as the left child of 70.

 
      50
     /  \
   30    70
  /  \  /
20   40 60
Step 7: Insert 80

  • Compare 80 with the root node 50.

  • Since 80 > 50, move to the right subtree (70).

  • Compare 80 with 70.

  • Since 80 > 70, it is inserted as the right child of 70.

 
      50
     /  \
   30    70
  /  \  /  \
20   40 60  80
Final BST

The final Binary Search Tree after inserting all elements is:

      50
     /  \
   30    70
  /  \  /  \
20   40 60  80

5. Construct a Huffman tree for the following character frequencies: A: 5, B: 9, C: 12, D: 13, E: 16, F: 45

Answer  : 

To construct a Huffman tree for the given character frequencies {A: 5, B: 9, C: 12, D: 13, E: 16, F: 45}, we follow the Huffman algorithm. 

Step 1: Initialize a Min-Heap

  • Create a min-heap (priority queue) with the characters and their frequencies:

     
    [A (5), B (9), C (12), D (13), E (16), F (45)]
Step 2: Build the Huffman Tree

  • Repeatedly combine the two nodes with the smallest frequencies until one node remains.

Iteration 1:

  • Extract A (5) and B (9).

  • Create a new node z1 with frequency 5 + 9 = 14.

  • Insert z1 into the min-heap.

Updated min-heap:

[C (12), D (13), z1 (14), E (16), F (45)]
Iteration 2:

  • Extract C (12) and D (13).

  • Create a new node z2 with frequency 12 + 13 = 25.

  • Insert z2 into the min-heap.

Updated min-heap:

[z1 (14), E (16), z2 (25), F (45)]
Iteration 3:

  • Extract z1 (14) and E (16).

  • Create a new node z3 with frequency 14 + 16 = 30.

  • Insert z3 into the min-heap.

Updated min-heap:

[z2 (25), z3 (30), F (45)]
Iteration 4:

  • Extract z2 (25) and z3 (30).

  • Create a new node z4 with frequency 25 + 30 = 55.

  • Insert z4 into the min-heap.

Updated min-heap:

[F (45), z4 (55)]
Iteration 5:

  • Extract F (45) and z4 (55).

  • Create a new node z5 with frequency 45 + 55 = 100.

  • Insert z5 into the min-heap.

Updated min-heap:

[z5 (100)]

Now the min-heap has only one node, so the Huffman tree is complete.

Step 3: Construct the Huffman Tree

The final Huffman tree is:

          z5 (100)
         /      \
     F (45)    z4 (55)
              /      \
         z2 (25)    z3 (30)
        /      \    /      \
   C (12)  D (13) z1 (14) E (16)
                 /      \
             A (5)    B (9)
Step 4: Assign Huffman Codes

  • Traverse the Huffman tree from the root to each leaf node.

  • Assign 0 for left branches and 1 for right branches.

Codes:

  • F: Path = 0 → Code = 0

  • C: Path = 1 → 0 → 0 → Code = 100

  • D: Path = 1 → 0 → 1 → Code = 101

  • A: Path = 1 → 1 → 0 → 0 → Code = 1100

  • B: Path = 1 → 1 → 0 → 1 → Code = 1101

  • E: Path = 1 → 1 → 1 → Code = 111

6. Compare and contrast tree terminologies such as height, depth, degree, and level with examples.

Answer  :  
Key Differences

  1. Height vs Depth:

    • Height is measured from a node to the deepest leaf.

    • Depth is measured from the root to the node.

  2. Degree:

    • Refers to the number of children a node has.

  3. Level:

    • Levels start from 0 at the root and increase down the tree.

The comparison of tree terminologies such as height, depth, degree, and level, with the root at level 0:

1. Height

  • Definition: The height of a node is the number of edges on the longest path from the node to a leaf. The height of a tree is the height of its root.

  • Example:

     
        A
   / \
  B   C
     / \
    D   E

    • Height of node C is 1 (longest path: C → D or C → E).

    • Height of the tree (root A) is 2 (longest path: A → C → D or A → C → E).

2. Depth

  • Definition: The depth of a node is the number of edges from the root to that node. The depth of the root is 0.

  • Example:

     
        A
   / \
  B   C
     / \
    D   E

    • Depth of node A is 0.

    • Depth of node C is 1.

    • Depth of node E is 2.

3. Degree

  • Definition: The degree of a node is the number of children it has. The degree of a tree is the maximum degree of any node in the tree.

  • Example:

     
        A
   / \
  B   C
     / \
    D   E

    • Degree of node A is 2 (children: B and C).

    • Degree of node C is 2 (children: D and E).

    • Degree of node B is 0 (no children).

    • Degree of the tree is 2 (maximum degree of any node).

4. Level

  • Definition: The level of a node is its depth. The root is at level 0.

  • Example:

     
        A
   / \
  B   C
     / \
    D   E

    • Level of node A is 0.

    • Level of node C is 1.

    • Level of node E is 2.

Comparison Table
TermDefinitionExample (Tree above)
HeightLongest path from node to leaf.Height of C = 1, Height of tree = 2.
DepthNumber of edges from root to node.Depth of C = 1, Depth of E = 2.
DegreeNumber of children of a node.Degree of A = 2, Degree of B = 0.
LevelDepth of the node. Root is at level 0.Level of C = 1, Level of E = 2.

7. Compare different types of binary trees (strictly binary, full binary, complete binary) using diagrams.

Answer  :   
Key Differences

  1. Strictly Binary Tree:

    • Every node has 0 or 2 children.

    • No restriction on the level of leaf nodes.

  2. Full Binary Tree:

    • Every node has 0 or 2 children.

    • All leaf nodes must be at the same level.

  3. Complete Binary Tree:

    • Nodes can have 0, 1, or 2 children.

    • All levels except the last are fully filled, and the last level is filled from left to right.

Comparison of different types of binary trees—strictly binary, full binary, and complete binary—using definitions and diagrams:

1. Strictly Binary Tree

  • Definition: A binary tree where every node has either 0 or 2 children. No node has only one child.

  • Diagram:

     
          A
     / \
    B   C
   / \
  D   E

    • Node A has 2 children (B and C).

    • Node B has 2 children (D and E).

    • Nodes C, D, and E have 0 children.

2. Full Binary Tree

  • Definition: A binary tree where every node has either 0 or 2 children, and all leaf nodes are at the same level.

  • Diagram:

     
          A
     / \
    B   C
   / \ / \
  D  E F  G

    • Every node has 0 or 2 children.

    • All leaf nodes (D, E, F, G) are at the same level.

3. Complete Binary Tree

  • Definition: A binary tree where all levels are completely filled, except possibly the last level, which is filled from left to right.

  • Diagram:

     
          A
     / \
    B   C
   / \ /
  D  E F

    • All levels except the last are completely filled.

    • The last level is filled from left to right (F is filled, but G is missing).

Comparison Table
PropertyStrictly Binary TreeFull Binary TreeComplete Binary Tree
Node ChildrenEvery node has 0 or 2 children.Every node has 0 or 2 children.Nodes can have 0, 1, or 2 children.
Leaf NodesLeaf nodes can be at any level.All leaf nodes are at the same level.Leaf nodes are filled from left to right.
LevelsLevels may not be fully filled.All levels are fully filled.All levels except the last are fully filled.

8. Examine the conditions under which a complete binary tree can also be a full binary tree.

Answer  :     

A complete binary tree and a full binary tree are two distinct types of binary trees, but there are specific conditions under which a complete binary tree can also be a full binary tree. Let’s examine these conditions:

Definitions

  1. Complete Binary Tree:

    • All levels are completely filled, except possibly the last level.

    • The last level is filled from left to right.

  2. Full Binary Tree:

    • Every node has 0 or 2 children.

    • All leaf nodes are at the same level.

Conditions for Overlap

A complete binary tree can also be a full binary tree if and only if:

  1. All levels are completely filled, including the last level.

  2. Every node has exactly 0 or 2 children.

In other words, a complete binary tree is also a full binary tree when it is perfect.

Example

Consider the following binary tree:

        A
       / \
      B   C
     / \ / \
    D  E F  G

  • Complete Binary Tree: Yes, because all levels are completely filled.

  • Full Binary Tree: Yes, because every node has 0 or 2 children, and all leaf nodes are at the same level.

This tree satisfies both definitions, so it is both a complete binary tree and a full binary tree.

Counter example

Now consider this binary tree:

        A
       / \
      B   C
     / \
    D   E

  • Complete Binary Tree: Yes, because all levels except the last are completely filled, and the last level is filled from left to right.

  • Full Binary Tree: No, because node C has only 1 child (missing the right child).

This tree is a complete binary tree but not a full binary tree.

9. Construct a binary search tree (BST) using the following sequence of numbers: 50, 30, 70, 20, 40, 60, 80 and draw the resultant tree.

Answer  :     

A complete binary tree and a full binary tree are two distinct types of binary trees, but there are specific conditions under which a complete binary tree can also be a full binary tree. Let’s examine these conditions:

Definitions

  1. Complete Binary Tree:

    • All levels are completely filled, except possibly the last level.

    • The last level is filled from left to right.

  2. Full Binary Tree:

    • Every node has 0 or 2 children.

    • All leaf nodes are at the same level.

Conditions for Overlap

A complete binary tree can also be a full binary tree if and only if:

  1. All levels are completely filled, including the last level.

  2. Every node has exactly 0 or 2 children.

In other words, a complete binary tree is also a full binary tree when it is perfect.

Example

Consider the following binary tree:

        A
       / \
      B   C
     / \ / \
    D  E F  G

  • Complete Binary Tree: Yes, because all levels are completely filled.

  • Full Binary Tree: Yes, because every node has 0 or 2 children, and all leaf nodes are at the same level.

This tree satisfies both definitions, so it is both a complete binary tree and a full binary tree.

Counter example

Now consider this binary tree:

        A
       / \
      B   C
     / \
    D   E

  • Complete Binary Tree: Yes, because all levels except the last are completely filled, and the last level is filled from left to right.

  • Full Binary Tree: No, because node C has only 1 child (missing the right child).

This tree is a complete binary tree but not a full binary tree.

Table of Contents
Question Bank Short Answer
Next
Piyu's CS

Computer Science Education

Contact Us

info@piyuscs.com