UGC NET

JRF December 2024

Computer
Data Structures and Algorithms DPP: 3
Binary Tree and Binary Search Tree

Q1 What is the time complexity of balanced binary (B) key sequence III only
search tree : (C) Key sequence II only
2)
(A) O(n) (B) O(n (D) None of these
(C) O(log n) (D) O(n log n)
Q5 Consider the following binary search tree:
Q2 Which following statement is /are false for a If we remove 18 node, which of the node from
binary tree? the right subtree will be the new root?
I: A binary tree is called a perfect binary tree if
every non-leaf node of it has two children and all
leaf nodes are at the same level. .
II:A complete binary tree is said to be a proper
binary tree where all leaves have the same depth.
III: A perfect binary tree with n leaves always
contains (2n-1)nodes.
IV All the nodes of the perfect binary tree of 15
depth d must be at level d. / \
(A) Only I 5 18
(B) Only II and III /\ \
(C) Only IV 3 12 20
(D) Only II /\ /\
10 13 21 23
Q3 The number of nodes in a full binary tree of
/
depth 6 is
6
(A) 50 (B) 60
(A) 15 (B) 23
(C) 64 (D) 63
(C) 20 (D) 21
Q4 A binary search tree stores pages in the range
Q6 Consider the following binary search tree:
40-550 and considers the following sequence of
keys.
I) 87,537,102,439,285,376,305
II) 52,97,121,195,242,381,472
III) 142,248,520,386,345,270,307
IV) 550, 149,507,395,463,402,270
Suppose the binary search tee has been
unsuccessfully searched for key 273. Which of 15
the above sequence list nodes in the order in / \
which we could have encountered them in the 5 18
search /\ \
(A) key sequence I only 3 12 20

Android App | iOS App | PW Website

 UGC NET

/\ /\ Q9 Match the following List I with List II :

10 13 21 23 List I Lits II
/ A. Implementing
I. n+1
6 dictionaries.
Where will new node 25 be inserted? B. Null branches with II. Binary
(A) right chid of 20 node n nodes in a search
(B) right child of 23 complete binary tree tree
(C) right child of 21
III. less
(D) right child of 13 C. BST left node
than to
should be
Q7 A binary search tree is constructed by inserting root node
the following numbers in order : IV. greater
D. BST right node
50,15,62,5,20,58,91,3,8,37,60,24 than to
should be
the number of nodes in the right sub-tree will root node
be____. Choose the correct answer from the options
(A) 7 (B) 4 given below:
(C) 5 (D) 8 (A) A-II, B-I, C-III,D-IV
(B) A-I, B-II, C-IV, D-III
Q8 Match the following List I with List II :
(C) A-II, B-I, C-IV, D-III
List I Lits II (D) A-II, B-IV, C-I, D-III
I. Every level
except the last Q10 Which of the following is the correct sequence of
A. Full binary steps to perform a search in a binary search tree?
level must be
tree 1. Compare the element being searched with the
completely
filled. root value of the tree.

II. If every node 2. If the root value does not match, determine if
B. Complete the target is greater or smaller than the root
has 0 or 2
binary tree element.
children
3. If the root element is smaller, move to the right
C. BST max-
III. ceil(log2n) subtree or if greater, move to the left subtree.
height
4. If the root value matches the target element,
D. BST min- IV. n-1(number
return the node's location
height of node)
5. Repeat the process until a match is found.If
target value can't be found return NULL.
(A) A-II, B-I, C-III,D-IV
(A) 1, 4, 2, 3, 5 (B) 1, 3, 2, 4, 5
(B) A-II, B-I, C-IV, D-III
(C) 1, 5, 2, 3, 4 (D) 1, 5, 3, 4, 2
(C) A-II, B-IV, C-I, D-III
(D) A-III, B-I, C-IV, D-II

Android App | iOS App | PW Website

 UGC NET

Answer Key
Q1 (C) Q6 (B)

Q2 (C) Q7 (B)

Q3 (D) Q8 (B)

Q4 (B) Q9 (A)

Q5 (C) Q10 (A)

Android App | iOS App | PW Website

 UGC NET

Hints & Solutions

Q1 Text Solution: far left.
The Time complexity of a Balanced Binary A full binary tree is a tree in which every node
Searched Tree isO( log n), because as it traverses other than the leaves has two children. A
the tree, it either goes left or right eliminating complete binary tree is a binary tree in which
half of the whole Tree. For an unbalanced Binary every level, except possibly the last, is
search tree, the time complexity is O(n), it's completely filled, and all nodes are as far left as
basically similar to a linear search. possible.
So option C is the correct answer. Q4 Text Solution:
Q2 Text Solution: I) 87,537,102,439,285,376,305
Statement I: A binary tree is said to be ‘perfect’ if when inserting 273 it enters the left side node of
all the internal nodes have strictly two children 305 but 273 < 285 then the search always goes
and all leaf nodes are at the same level. to the left side. So here BST property can't be
followed.

Statement II: A complete binary tree of depth d is

the perfect binary tree where all of the leaves are
at level d, that is every external or leaf node is at
the same level or same depth within a tree.
Statement III: A perfect binary tree with n leaves II) 52,97,121,195,242,381,472 sequence is not
always contains (2n-1)nodes. If n (1): a perfect going in the right direction. 381>273 does not
binary tree with 1 leaf contains 2(1)-1 = 1 node. follow BST property.
Statement IV: All the nodes of the perfect binary
tree of depth d must be at level d.
This statement is wrong because any node at a
level less than d-1 has two children.
So option C is the correct answer.

Q3 Text Solution:
The number of nodes in a full binary tree of
depth 6 is 63.
The maximum number of nodes in a binary tree
of depth k is : 2k − 1, k >= 1.
26 − 1 = 64 − 1 = 63
The maximum possible number of null links in a
complete binary tree of n nodes is (n+1), where
only 1 node exists in the bottom-most level to the

Android App | iOS App | PW Website

 UGC NET

III) 142,248,520,386,345,270,307 correct tree • Right subtree of 18: {20, 21, 23}
270<273 and subtree in the right side of 270. • The successor node (the smallest node in the
right subtree of 18) is 20.
Therefore, if we remove the node with value 18
from the binary search tree, node 20 will be the
new root of the tree.
After removing the node with value 18 from the
given binary search tree, and making 20 the new
root, the resulting tree structure would be as
follows:
20
/ \
15 21
/ \ \
5 18 23
/\ \
IV) 550, 149,507,395,463,402,270 after 395 sub 3 12 20
trees are wrong because 395<402 and 402 is on /\ /\
the left side. 10 13 21 23
/
6
Here's how the nodes are arranged:
Root: 20
Left subtree of 20: {15, 5, 3, 12, 10, 6}
Right subtree of 20: {21, 23}
After Node 18 has been removed.The structure
maintains the binary search tree property where
all nodes in the left subtree of a node have
values less than the node's value, and all nodes in
the right subtree have values greater than the
node's value.
So option C is the correct answer.

Q6 Text Solution:
The node25 will be inserted at _____
15<25 we will traverse towards the right sub-tree
18<25 we will traverse towards the right sub-tree
Q5 Text Solution:
20<25 we will traverse toward the right sub-tree
In a binary search tree:
23<25 so it will be inserted as the right child of
• Nodes in the right subtree of a node have
23.
values greater than the node itself.
Thus option B is the correct answer.
• The successor node for replacing the removed
node should typically be the smallest node in Q7 Text Solution:
its right subtree (in terms of value). To determine the number of nodes in the right
Looking at the right subtree of 18: subtree of the root (50) in the BST formed by
inserting the numbers 50, 15, 62, 5, 20, 58, 91, 3,

Android App | iOS App | PW Website

 UGC NET

8,37, 60, 24, let's make BST structure: the last level and the last level has all keys as left
as possible.
List I C: Suppose there is a binary search tree that
contains n number of nodes. So the maximum
height will be "n-1" for this BST.
List I D: The minimum height of BST will be "ceil
(log2n)".
Thus option B is the correct answer.

Q9 Text Solution:
A: Major Real-Time Application Of Binary Search
Tree
• They are used in implementing dictionaries.
• They are used in spelling checking.
• BST is used for indexing in DBMS. etc
B: The maximum possible number of null links
Counting the Nodes in the Right Subtree of the
(i.e., absent children of the nodes) in a complete
Root (50)
binary tree of n nodes is (n+1).
Now, we can count the number of nodes in the
C and D: In a binary search tree, the elements are
right subtree of the root (50):
arranged following a specific order. The rule is
• Right Subtree:
that the value of a left node must be smaller
• Root: 62
than its parent node, and the value of a right
• Left Subtree of 62:
node must be greater than its parent node.
• Root: 58
So option A is the correct answer.
• Right Child: 60
• Right Subtree of 62: Q10 Text Solution:
• Root: 91 Following is the correct sequence of steps to
Nodes in the Right Subtree of 50 Nodes under perform a search in a binary search tree-
62: 1. Compare the element being searched with the
• 62 root value of the tree.
• 58 2. If the root value matches the target element,
• 60 return the node's location
• 91 3. If the root value does not match, determine if
Total Count = 4 nodes The number of nodes in the target is greater or smaller than the root
the right subtree of 50 is 4. element.
4. If the root element is smaller, move to the right
Q8 Text Solution:
subtree or if greater, move to the left subtree.
List I A: A Binary Tree is a full binary tree if every
5. Repeat the process until a match is found. If
node has 0 or 2 children.
the target value can't be found return NULL.
List I B: A Binary Tree is a Complete Binary Tree if
So option A is the correct answer.
all the levels are completely filled except possibly

Android App | iOS App | PW Website