Take This Data Structure - Binary Trees Quiz
-
A full binary tree with 6 non-leaf nodes contains a maximum of
-
13 nodes
-
6 nodes
-
9 nodes
-
11 nodes
-
About This Quiz
Have you got knowledge about the binary trees in data structure? To test your knowledge, take this tree data structure quiz. We have got simple as well as complex questions for your practice. You can take up the quiz and pick the maximum correct answers to get a good score. Don't feel bad even if you miss out on some See morequestions, as you will get the correct one there and then. This quiz will not only test your knowledge but enhance it too. All the best!
Quiz Preview
- 2.
A binary search tree is generated by inserting in order the following integers: 50, 15, 12, 25, 40, 58, 81, 31, 18, 37, 60, 24 The number of the node in the left subtree and right subtree of the root, respectively, is
-
(4, 7)
-
(7,4)
-
(8, 3)
-
(3,8)
Correct Answer
A. (8, 3)Explanation
The correct answer is (8, 3) because when we insert the given integers in order into a binary search tree, the left subtree of the root will have 8 nodes (12, 15, 18, 24, 25, 31, 37, 40) and the right subtree will have 3 nodes (58, 60, 81).Rate this question:
-
- 3.
The following routine displays the ………….. element in a binary search tree. public void BST(Tree root) { while(root.left() != null) { root = root.left(); } System.out.println(root.data()); }
Correct Answer
minimumExplanation
The given routine is traversing the binary search tree by always moving to the left child until there is no left child left. This means that it is finding the leftmost (minimum) element in the binary search tree. The routine then prints the data of the root node, which corresponds to the minimum element in the tree.Rate this question:
- 4.
If this tree is used for sorting, then new no 8 should be placed as the
-
Left child of the node labeled 6
-
Right child of the node labeled 14
-
Right child of the node labeled 6
-
Left child of the node labeled 9
Correct Answer
A. Left child of the node labeled 9Explanation
If this tree is used for sorting, the new number 8 should be placed as the left child of the node labeled 9. This is because in a binary search tree used for sorting, smaller values are placed to the left of a node and larger values are placed to the right. Since 8 is smaller than 9, it should be placed as the left child of the node labeled 9.Rate this question:
-
- 5.
When you construct a BST with the preorder traversal of a binary search tree 10, 4, 3, 5, 11, 12,21,36, then which of the following are leaf nodes?
-
5,3,4
-
5,3,12
-
3,5,12
-
3,5,36
Correct Answer
A. 3,5,36Explanation
The leaf nodes in a binary search tree are the nodes that do not have any children. In the given preorder traversal, the leaf nodes are 3, 5, and 36. This is because these nodes do not have any children in the tree.Rate this question:
-
- 6.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering of natural numbers. Will the in-order traversal sequence of the resultant tree be the same for the numbers in the sequence 9,7, 5, 1, 8, 3, 2,6, 0, 4 (Yes / No)
-
Yes
-
No
Correct Answer
A. YesExplanation
The in-order traversal sequence of a binary search tree is determined by the order in which the elements are inserted. In this case, the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order, resulting in a specific structure of the tree. When the sequence 9, 7, 5, 1, 8, 3, 2, 6, 0, 4 is inserted in the same order, it will result in the same structure of the tree. Therefore, the in-order traversal sequence of the resultant tree will be the same for both sequences.Rate this question:
-
- 7.
The following numbers are inserted into an empty binary tree and binary search tree in the given order: 20,10, 1, 3, 5, 15, 12, 16,34,87,35. The height of the binary tree and binary search tree, respectively, is.
-
4,4
-
3,3
-
3,4
-
4,3
Correct Answer
A. 4,4Explanation
Binary Search Tree (BST)
The BST is built by inserting the elements one by one in the given order:
20 (root)
10 (left of 20)
1 (left of 10)
3 (right of 1)
5 (right of 3)
15 (right of 10)
12 (left of 15)
16 (right of 15)
34 (right of 20)
87 (right of 34)
35 (left of 87)
The height of a BST is defined as the number of edges in the longest path from the root to a leaf. In this case, the height is 4 (counting the edges from the root 20 to the leaf 35).
Binary Tree
A binary tree's height is not inherently defined by a specific order of insertion. However, if we consider a binary tree where the same sequence is inserted in the same order, assuming we maintain the structure as given, we would get a similar height.
In this case, if we look at the way the elements are inserted and maintain a similar structure as the BST without reordering for balance, the height remains the same.
Conclusion
The height of the binary search tree is 4, and if we maintain the structure as mentioned above for a binary tree, it is also 4.
so the answer 4, 4
Rate this question:
-
- 8.
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
-
10, 20, 15, 23, 25, 35, 42, 39, 30
-
15, 10, 25, 23, 20, 42, 35, 39, 30
-
15, 20, 10, 23, 25, 42, 35, 39, 30
-
15, 10, 23, 25, 20, 35, 42, 39, 30
Correct Answer
A. 15, 10, 23, 25, 20, 35, 42, 39, 30Explanation
The given preorder traversal sequence, 30, 20, 10, 15, 25, 23, 39, 35, 42, corresponds to the following binary search tree. The tree has a root node with a value of 30, and on the left subtree, there are nodes with values 20, 10, 15, and 25. The right subtree has nodes with values 39, 35, and 42. Additionally, there is a node with a value of 23 as the left child of the node with the value 25. The postorder traversal of this tree is 15, 23, 10, 25, 20, 35, 42, 39, 30. This sequence represents the order in which the nodes would be visited in a postorder traversal, starting from the leftmost leaf, then traversing the right subtree, and finally visiting the root node.Rate this question:
-
- 9.
Construct a binary tree by using inorder and preorder sequences given below. Inorder: D,B,H,E,I,A,F,C,G Preorder: A,B,D,E,H,I,C,F,G Find the postorder traversal
-
D,H,E,I,B,F,G,C,A
-
A,C,G,F,B,I,E,H,D
-
D,H,I,E, B,F,G,C ,A
-
D,H,I,E,G,F,B,C,A
Correct Answer
A. D,H,I,E, B,F,G,C ,AExplanation
The postorder traversal of a binary tree is obtained by visiting the left subtree, then the right subtree, and finally the root node. In this case, the correct postorder traversal is D, H, I, E, B, F, G, C, A. This means that the left subtree of the root node contains the nodes D, H, I, E, and B, the right subtree contains the nodes F, G, and C, and the root node is A.Rate this question:
-
- 10.
Which of the two key sequences construct the same BSTs? Select the ones you like
-
A1[ ] = {8, 3, 6, 1, 4, 7, 10, 14, 13} A2[ ] = {8, 10, 14, 3, 6, 4, 1, 7, 13}
-
B1[ ]= {15, 10, 25, 23, 20, 42, 35, 39, 30} B2[ ] ={15, 20, 10, 23, 25, 42, 35, 39, 30}
-
C1[ ]={7, 5, 1, 8, 3, 6, 9, 4, 2} C2[ ]={ 9,7, 5, 1, 8, 3, 2,6, 4}
-
D1[ ]={15, 10, 25, 23, 20, 42, 35, 39, 30} D2[ ]={ 15,35,39,10,25,20,23,42,30}
Correct Answer
A. A1[ ] = {8, 3, 6, 1, 4, 7, 10, 14, 13} A2[ ] = {8, 10, 14, 3, 6, 4, 1, 7, 13}Explanation
Both A1 and A2 have the same elements, just in a different order. However, the order of elements in a key sequence does not matter when constructing a BST. As long as the elements are the same, the resulting BST will be the same.Rate this question:
-
- 11.
Which of the following is AVL Tree?
-
Only A
-
A and C
-
A, B, and C
-
Only B
Correct Answer
A. Only BExplanation
An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. Only option B can be an AVL tree because it satisfies this condition. Option A does not have a balanced structure, and option C includes a node with a height difference of more than one.Rate this question:
-
- 12.
Consider the given AVL Tree. If node 2 is added to this, then the parent node of 5 in a balanced tree is
-
8
-
4
-
11
-
12
Correct Answer
A. 4Explanation
When node 2 is added to the given AVL tree, it becomes unbalanced. To balance the tree, a right rotation is performed on node 8. After the rotation, node 4 becomes the parent of node 5, which is the correct answer.Rate this question:
-
- 13.
What is the maximum height of any AVL tree with 7 nodes? Assume that the height of a tree with a single node is 0.
-
2
-
3
-
4
-
5
Correct Answer
A. 3Explanation
The maximum height of any AVL tree with 7 nodes is 3. This is because an AVL tree is a self-balancing binary search tree, and its height is always kept minimal by performing rotations to balance the tree. With 7 nodes, the tree can have a maximum height of 3, where the root node has two child nodes, each with two child nodes, resulting in a balanced tree.Rate this question:
-
- 14.
Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19 after deleting node 30 from the AVL tree then the root node of the resultant tree is
-
18
-
20
-
30
-
15
Correct Answer
A. 18Explanation
After inserting the given sequence of elements into the AVL tree and deleting node 30, the resultant tree will have 18 as the root node. This is because the AVL tree is a self-balancing binary search tree, and after the deletion of node 30, the tree will be rebalanced to maintain the AVL property. The root node is chosen based on the balance factors of the nodes, and in this case, the balance factors of the nodes indicate that 18 should be the root node.Rate this question:
-
- 15.
Show the result when an initially empty AVL tree has keys 1 through 8 inserted in order. Then the node in the last level will be
-
8
-
7,8
-
7
-
6,7
Correct Answer
A. 8Explanation
When keys 1 through 8 are inserted in order into an initially empty AVL tree, the tree will be balanced and the nodes will be arranged in a way that each level has the maximum number of nodes possible. Since the last level represents the deepest level of the tree, it will contain the remaining nodes after all the previous levels are filled. In this case, the last level will have only one node, which is 8. Therefore, the node in the last level will be 8.Rate this question:
-
- 16.
AVL tree of height 4 contains ……………. minimum possible number of nodes
-
11
-
16
-
14
-
10
Correct Answer
A. 16Explanation
To determine the minimum number of nodes in an AVL tree of height 4, we need to use the AVL property:
For an AVL tree of height h, the minimum number of nodes, N(h), can be expressed as:
N(h) = N(h-1) + N(h-2) + 1
where:
N(h) is the minimum number of nodes in an AVL tree of height h.
N(h-1) is the minimum number of nodes in the left subtree.
N(h-2) is the minimum number of nodes in the right subtree.
1 represents the root node.
Using this formula recursively:
N(4) = N(3) + N(2) + 1 = [N(2) + N(1) + 1] + [N(1) + N(0) + 1] + 1 = [(3 + 1 + 1) + (1 + 0 + 1)] + [(1 + 0 + 1) + (0 + 0 + 1)] + 1 = (5 + 3) + (3 + 1) + 1 = 16Rate this question:
-
- 17.
To restore the AVL property after inserting an element, we start at the insertion point and move towards the root of that tree. Is this statement true?
-
True
-
False
Correct Answer
A. TrueExplanation
The given statement is true. After inserting an element in an AVL tree, we need to restore the AVL property by checking the balance factor of each node on the path from the insertion point to the root. If the balance factor of any node becomes greater than 1 or less than -1, we need to perform rotations to rebalance the tree. By starting at the insertion point and moving towards the root, we ensure that we check and fix the balance of each node in the path, thus restoring the AVL property.Rate this question:
-
- 18.
Given an empty AVL tree, how would you construct an AVL tree when a set of numbers are given without performing any rotations?
-
Just build the tree with the given input
-
Find the median of the set of elements given, make it a root
-
Use trial and error
-
Use dynamic programming to build the tree
Correct Answer
A. Find the median of the set of elements given, make it a rootExplanation
To construct an AVL tree without performing any rotations, we can find the median of the set of elements given and make it the root of the tree. This approach ensures that the tree is balanced as the median divides the set into two equal halves. The elements smaller than the median will be inserted into the left subtree, and the elements greater than the median will be inserted into the right subtree. By recursively applying this process to the left and right subtrees, we can construct a balanced AVL tree without the need for rotations.Rate this question:
-
- 19.
The balance factor of node A was 0 and, a node was inserted to the left of node A then
-
It is required to balance Node A
-
It is required to balance the Right child of A
-
It is required to balance the Parent of node A
-
Balancing may or may not be required for A
Correct Answer
A. It is required to balance the Parent of node AExplanation
When a node is inserted to the left of node A, it causes an imbalance in the parent of node A. This is because the left subtree of the parent becomes heavier than the right subtree. To maintain the balance of the tree, it is required to balance the parent of node A by performing rotation operations if necessary.Rate this question:
-
- 20.
AVL is traversed in the following order recursively: Right, root, left. The output sequence will be in
-
Descending order
-
Ascending order
-
Level-wise order
-
No specific order
Correct Answer
A. Descending orderExplanation
The AVL tree is traversed in the order of right, root, left recursively. This means that the right subtree is visited first, then the root node, and finally the left subtree. Since the right subtree is visited first, followed by the root node, and then the left subtree, the output sequence will be in descending order.Rate this question:
-
- 21.
Given the code, choose the correct option that is consistent with the code. (Here A is the heap) build(A,i) left-> 2*i right->2*i +1 temp- > i if(left<= heap_length[A] and A[left] >A[temp]) temp -> left if (right = heap_length[A] and A[right] > A[temp]) temp->right if temp!= i swap(A[i],A[temp]) build(A,temp)
-
Build function of max heap
-
Build function of min heap
-
Build function of any heap
-
Search element in any heap
Correct Answer
A. Build function of max heapExplanation
The given code is implementing the build function for a max heap. It starts by assigning the index i to a temporary variable temp. Then, it checks if the left child of i (2*i) is within the heap length and if the value at the left child is greater than the value at temp. If this condition is true, it updates temp with the index of the left child. Similarly, it checks if the right child of i (2*i+1) is within the heap length and if the value at the right child is greater than the value at temp. If this condition is true, it updates temp with the index of the right child. Finally, if temp is not equal to i, it swaps the values at indices i and temp and recursively calls the build function. This process ensures that the heap property is maintained, resulting in a max heap. Therefore, the correct option is "build function of max heap".Rate this question:
-
- 22.
State the complexity of the algorithm given below. int function(vector<int> arr) int len=arr.length(); if(len==0) return; temp=arr[len-1]; arr.pop_back(); return temp;
-
O(n)
-
O(logn)
-
O(1)
-
O(n logn)
Correct Answer
A. O(1)Explanation
The given algorithm has a constant time complexity of O(1). This is because the algorithm performs a fixed number of operations, regardless of the size of the input vector. It checks the length of the vector, performs a single operation to retrieve the last element, and then removes the last element from the vector. The number of operations remains constant, regardless of the size of the input, hence the time complexity is O(1).Rate this question:
-
- 23.
An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in the order of
-
O(n*n*logn)
-
O(n*logn)
-
O(n*n)
-
O(n *logn *logn)
Correct Answer
A. O(n*logn)Explanation
When building a heap from an array with n elements, the time complexity can be determined by the number of comparisons and swaps needed to satisfy the heap property. In each step, we compare an element with its parent and potentially swap them if necessary.
The number of comparisons and swaps required can be represented as O(n*logn), where n is the number of elements in the array. This is because the height of a heap is logarithmic with respect to the number of elements, and at each level, we perform a constant number of comparisons and swaps.
Therefore, the time complexity of building a heap from an array is O(n*logn).Rate this question:
-
- 24.
If we implement heap as a maximum heap, adding a new node of value 15 into it. What value will be at leaf nodes of the left subtree of the heap?
-
2
-
7
-
3
-
15
Correct Answer(s)
A. 2
A. 7
A. 3Explanation
When a new node is added to a maximum heap, it is inserted at the next available leaf node in a left-to-right fashion. In this case, the new node with a value of 15 will be inserted as the leftmost leaf node in the left subtree. Therefore, the values at the leaf nodes of the left subtree will remain the same as before the insertion, which are 2, 7, and 3.Rate this question:
-
- 25.
What will be the position of 65 when a max heap is constructed on the input elements 5, 70, 45, 7, 12, 15, 13, 65, 30, 25?
-
Root
-
Last level
-
Second level
-
Anywhere in heap
Correct Answer
A. Second levelExplanation
The position of 65 will be on the second level of the max heap. In a max heap, the largest element is always at the root, and the elements are arranged in a complete binary tree structure. The first level consists of only the root node, the second level consists of the left and right child of the root node, and so on. Since 65 is not the largest element, it will not be at the root, but it will be on the second level.Rate this question:
-
- 26.
Does there exist a heap with seven distinct elements so that the In order traversal gives the element in sorted order?
-
Yes
-
No
-
Both I and II
-
None of these
Correct Answer
A. NoExplanation
No, there does not exist a heap with seven distinct elements such that the in-order traversal gives the elements in sorted order. In a heap, the elements are arranged in a specific order based on their priority, with the highest priority element at the root. The in-order traversal of a heap does not guarantee a sorted order because it follows a specific pattern of visiting the left child, then the root, and then the right child. Therefore, it is not possible for the in-order traversal of a heap to give the elements in sorted order.Rate this question:
-
- 27.
Given a binary-max heap. The elements are stored in an array as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?
-
14,13,8,12,10
-
14,12,13,10,8
-
14,13,12,8,10
-
14,13,12,10,8
Correct Answer
A. 14,13,12,8,10Explanation
The given binary-max heap is represented by the array [25, 14, 16, 13, 10, 8, 12]. In a binary-max heap, the maximum element is always at the root. The first delete operation will remove the root element, which is 25, and replace it with the last element in the array, which is 12. Then, the heap property is restored by comparing the new root with its children and swapping if necessary. After the first delete operation, the array becomes [12, 14, 16, 13, 10, 8]. The second delete operation will remove the new root, which is 12, and replace it with the last element in the array, which is 8. Again, the heap property is restored, resulting in the final array [8, 14, 16, 13, 10]. Therefore, the correct answer is 14,13,12,8,10.Rate this question:
-
- 28.
Which of the below statements is/are TRUE?
-
The smallest element in a max-heap is always at a leaf node.
-
The second largest element in a max-heap is always a child of the root node.
-
A max-heap can be constructed from a binary search tree in Θ(n) time.
-
A binary search tree can be constructed from a max-heap in Θ(n) time.
Correct Answer(s)
A. The smallest element in a max-heap is always at a leaf node.
A. The second largest element in a max-heap is always a child of the root node.
A. A max-heap can be constructed from a binary search tree in Θ(n) time.Explanation
The first statement is true because in a max-heap, the largest elements are always at the higher levels of the heap, and the smallest elements are always at the leaf nodes.
The second statement is false because the second largest element in a max-heap can be anywhere in the heap, not necessarily a child of the root node.
The third statement is true because a max-heap can be constructed from a binary search tree in linear time, meaning the time complexity is Θ(n).
The fourth statement is false because a binary search tree cannot be constructed from a max-heap in linear time. The time complexity for this conversion is not Θ(n).Rate this question:
-
- 29.
Consider the following array of elements 89,19,50,17,12,15,2,5,7,11,6,9,100,98 then the minimum number of interchanges needed to convert it into max-heap is
-
4
-
5
-
2
-
3
Correct Answer
A. 5Explanation
To convert the given array into a max-heap, we need to arrange the elements in such a way that each parent node is greater than or equal to its children. The minimum number of interchanges needed can be determined by counting the number of times we need to swap elements to satisfy this condition. By applying the necessary interchanges, we can transform the array into a max-heap. Therefore, the correct answer is 5.Rate this question:
-
.webp "Consider the given AVL Tree. If node 2 is added to this, then the parent node of 5 in a balanced tree is")
Quiz Review Timeline (Updated): Jun 28, 2024 +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Jun 28, 2024Quiz Edited by
ProProfs Editorial Team
Expert Reviewed by
Samy Boulos -
Jun 30, 2020Quiz Created by
Akilacse
Back to top