Tree MCQ Quiz - Objective Question with Answer for Tree - Download Free PDF

The correct answer is Each node has a thread connecting it to its predecessor or successor

Key Points

• In a threaded binary tree, nodes may have threads (pointers) that connect them to either their in-order predecessor or successor.
• These threads provide a way to efficiently traverse the tree without the need for recursive calls or explicit stacks.
• Nodes with two children are typically called internal nodes, and nodes with one or no children are leaves. The threads in a threaded binary tree help in traversing the tree in in-order without the need for additional space or recursive function calls.

The correct answer is option 2: 2^k+1 − 1

Key Points

• In a binary tree, each level can contain at most twice the number of nodes as the previous level.
• If height k means the root is at level 0 and the last level is k, then total levels = k + 1.
• The maximum number of nodes in such a binary tree is given by the sum of the geometric progression:
  • Nodes = 1+2+4+⋯+2k=2k+1−1" id="MathJax-Element-203-Frame" role="presentation" style="position: relative;" tabindex="0">1+2+4+⋯+2k=2k+1−11+2+4+⋯+2k=2k+1−1 $1 + 2 + 4 + \dots + 2^k = 2^{k+1} - 1$
• This is the formula for the number of nodes in a perfect binary tree of height k.

Additional Information

• 2^k − 1: This would be valid if height was defined as number of levels minus one.
• 2^k−1 + 1 and 2^k + 1: Incorrect and do not follow from the geometric progression formula.
• Therefore, for height k starting from root at 0, maximum nodes = 2k+1−1" id="MathJax-Element-204-Frame" role="presentation" style="position: relative;" tabindex="0">2k+1−12k+1−1 $2^{k+1} - 1$

Hence, the correct answer is: option 2: 2^k+1 − 1

The correct answer is option 3: To deal with relationships that involve more than two tables

Key Points

• An N-ary association in a database refers to a relationship that involves N entities (or tables), where N ≥ 3.
• It is used when the relationship cannot be accurately or efficiently represented using just binary (2-table) associations.
• Commonly modeled using a relationship table that includes foreign keys referencing each of the N participating entities.

Additional Information

• Option 1: Parent-child relationships are typically represented using recursive relationships or 1:N binary associations.
• Option 2: One-to-many is a 2-entity (binary) relationship, not N-ary.
• Option 4: Inheritance is represented using generalization/specialization hierarchies, not N-ary associations.

Hence, the correct answer is: option 3: To deal with relationships that involve more than two tables

The correct answer is Multilevel sparse indices.

Key Points

• Non-leaf nodes of a B+ tree structure form multilevel sparse indices, which are crucial for its efficiency and performance.
• In a B+ tree, all the actual data records are stored in the leaf nodes, while the non-leaf nodes (or internal nodes) store the keys that act as pointers to guide the search process.
• The non-leaf nodes do not store every key, only enough to direct the search to the appropriate leaf node, making the indices sparse.
• This structure helps in reducing the height of the tree, thus speeding up the search, insert, and delete operations.
• Multilevel indexing means that the tree is structured in multiple levels (root, intermediate levels, and leaf nodes), where each level helps narrow down the search space progressively.
• The B+ tree is a balanced tree, meaning all the leaf nodes are at the same level, which ensures consistent and predictable performance.

Additional Information

• B+ trees are widely used in database indexing and file systems due to their efficiency in handling large amounts of data.
• They are an extension of B-trees, with the primary difference being that in B+ trees, all values are stored at the leaf level, and internal nodes only store keys.
• This structure ensures that sequential traversal of the data can be done efficiently by following the linked leaf nodes.
• Because of the multilevel sparse indexing, B+ trees are well-suited for range queries and ordered traversals.
• B+ trees maintain balance by splitting and merging nodes as necessary during insertions and deletions, ensuring that the tree remains balanced with minimal height.

Explanation:
In a full binary tree, each level contains nodes that follow the pattern:

Level 0: 2⁰ = 1 node

Level 1: 2¹ = 2 nodes

Level 2: 2² = 4 nodes

...

Level n: 2ⁿ nodes

So, the number of nodes at the nth level is given by 2ⁿ

Final Answer: Option 3) 2ⁿ ✅

Concept:

A binary tree can be traversed in three ways:

1. Preorder = (Root, Left subtree, Right Subtree)
2. Inorder = (Left subtree, Root, Right Subtree)
3. Postorder = (Left Subtree, Right subtree, Root)

Explanation:

In case of Binary Search Trees (BST), inorder traversal always sorts the tree nodes into ascending order.

Inorder traversal is 10, 11, 12, 15, 16, 18, 19, 20

Pre-order traversal is 15, 10, 12, 11, 20, 18, 16, 19.

In preorder traversal, the first node would be tree root and values less than root would be part of left

subtree and values greater than root node would form right subtree. So the resultant BST is:

Required Binary Search Tree:

Maximum nodes in Graph with height 5:

Maximum number of nodes = 1 + 2 + 4 + 8 + 16 + 32 = 6 

Minimum nodes in Graph with height 5:

Minimum number of nodes = 6 

Tips and Tricks:

If nmax is the maximum number of nodes and H height of in a binary search tree, then

n_max = 2H+1 – 1

put H = 5

n_max = 2H+1 – 1 = 2⁶ - 1 = 63

If n is the minimum number of nodes and H is the height of in a binary search tree, then

n_min = H + 1

put H = 5

nmin = 5  + 1 = 6

Answer: 1 to 1

Explanation: 

Consider the following Complete Binary Tree

A - {A, B, C}

B - {A, B, D}

Set A contains the first 3 elements obtained while Performing BFS.

Set B contains the first 3 elements obtained while performing DFS.

B={A, B, D} ( with DFS multiple Sequences are possible you can select anyone Answer to this Question will be same for all those sequences).

| A - B | 

=|{ A, B, C } – { A, B, D }| 

=|{C}| = 1

Explanation:

D = h + I = 2, E = G – k = -1, F = l - m =1 and G = n + o = 2

B = 2-(-1) = 3 and C= 1 + 2 = 3

A= 3 + 3 = 6 

Final tree:

Hence 6 is the correct answer.

Concept –

The in-order sequence can be found following the chronology of Left-> Root-> Right.

Finding the in-order traversal sequence, we get 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20.

The element that comes after 15 is its successor. It can be seen that 15’s successor is 17.

Explanation –

• In-order successor of a node is the minimum element in right subtree of the node in consideration.
• Here, in the right subtree of 15, 17 is the element with minimum value. Hence, 17 is 15’s in-order successor.
• Similarly, for finding the in-order predecessor of a node, the element with maximum value in left sub-tree is the answer. Here, 13 is 15’s in-order predecessor.

portant Point:

Tricks works only when the tree is Binary Search Tree.

Concepts:

Minimum height of the tree is when all the levels of BST are completely filled.

Maximum height of the binary search tree (BST) is the worst case when nodes are in skewed manner.

Formula:

Minimum height of the BST with n nodes is ⌈log₂ (n + 1)⌉ - 1

Maximum height of the BST with n nodes is n - 1.

Calculation:

Maximum height of the BST with 15 nodes 15 - 1 = 14

Diagram:

Minimum height of the BST with n nodes is ⌈log₂ (15 + 1)⌉ - 1 = 3

Diagram: 

Concept:

• In-order Traversal:  Left -> Root -> Right
• Pre-order Traversal:  Root -> Left -> Right
• Post-order Traversal :  Left -> Right -> Root

Binary tree:

Inorder Traversal: A, B, C, D, E, F, G, H, I 

Concept:

In a binary tree, a node can have maximum two children. If there are n nodes in binary tree, maximum height of the binary tree is n-1.

Tree with maximum height: n = 6

Height = 6 – 1 = 5

Longest path has length 4.

Formula:

L = I (n - 1) + 1

where, L = number of leaf nodes

I = number of internal nodes

n = n - ary tree

Explanation:

L = 19

n = 2 (as given tree is strictly binary tree)

19 = I (2 - 1) + 1

I = 18

Number of internal nodes = 18

Number of leaf nodes = 19

Total number of nodes = 18 + 19 = 37

Tips and Trick:

Number of internal node in a binary tree = number leaves - 1 = 19 - 1

Total nodes = number of leaf nodes + internal node = 19 + 18 = 37

Important Point: