programming
beginner
10 sample questions
Trees MCQ Practice Test
Understanding binary search trees (BSTs) and their properties.
Q1. A binary tree has nodes A, B, C, and D. A is the root. B is the left child of A, and C is the right child of A. D is the left child of B. What is the height of this tree?
Explanation: The longest path is A → B → D, which contains two edges, so the tree's height is 2.
Q2. A binary search tree is built by inserting the values [10, 5, 15, 3, 7, 12, 18] in that order. What is the third value visited in an inorder traversal?
Explanation: Inorder traversal of a BST lists values ascending: 3, 5, 7, 10, 12, 15, 18 - so the third value visited is 7. The stem now states the BST construction that the original left implicit.
Q3. A binary search tree is built by inserting the values [5, 3, 8, 1, 4, 7, 9] in that order. What sequence does an inorder traversal produce?
-
A. [1, 3, 4, 5, 7, 8, 9] ✓
-
B. [5, 3, 8, 1, 4, 7, 9]
-
C. [9, 8, 7, 5, 4, 3, 1]
-
D. [1, 4, 3, 5, 7, 9, 8]
Explanation: An inorder traversal of any BST yields the values in ascending order: [1, 3, 4, 5, 7, 8, 9]. The key was already correct; the stem now states the BST construction so the traversal is well defined.
Q4. A binary search tree is built by inserting the values [10, 5, 15, 3, 7, 12, 18] in that order. If we perform an inorder traversal, what will be the 4th value visited?
Explanation: Inorder traversal of a BST visits values in ascending order: 3, 5, 7, 10, 12, 15, 18. The 4th value visited is therefore 10. The original options omitted 10 and keyed '12', which is the 5th value.
Q5. What is the time complexity of inserting a new node at the end of a Binary Tree (implemented using a linked list for each node's children) in a way that the tree remains a binary tree?
-
A. O(1)
-
B. O(log n)
-
C. O(n) ✓
-
D. O(n log n)
Explanation: When inserting a new node at the end of a binary tree, we need to traverse the tree from the root to the last node, which takes O(n) time, where n is the number of nodes in the tree.
Q6. Given a binary tree node with a left child and a right child, what is the time complexity of traversing the tree using a recursive function?
-
A. O(1)
-
B. O(log n)
-
C. O(n) ✓
-
D. O(n^2)
Explanation: In a binary tree, each node can have at most two children. When traversing the tree using a recursive function, each node is visited once, resulting in a time complexity of O(n), where n is the number of nodes in the tree.
Q7. In a binary tree, what is the time complexity of traversing the tree using a recursive depth-first search?
-
A. O(n^2)
-
B. O(n log n)
-
C. O(n) ✓
-
D. O(log n)
Explanation: In a binary tree, traversing the tree using a recursive depth-first search involves visiting each node once, resulting in a time complexity of O(n), where n is the number of nodes in the tree.
Q8. Given a binary search tree where each node has a value and a list of child nodes, what is the correct way to insert a new node while maintaining the tree's property of having all values in the left subtree less than the current node's value and all values in the right subtree greater?
-
A. Insert the new node as a child of the root node
-
B. Find the node with the minimum value in the tree and insert the new node as its child
-
C. Find the node with the maximum value in the tree and insert the new node as its child
-
D. Compare the new node's value with the current node's value and insert it as a child of the node with the corresponding subtree ✓
Explanation: When inserting a new node into a binary search tree, we need to find the correct location to maintain the tree's property. We do this by comparing the new node's value with the current node's value and inserting it as a child of the node with the corresponding subtree.
Q9. Which data structure is best suited to represent a tree with nodes having variable number of children?
-
A. Linked List
-
B. Stack
-
C. Queue
-
D. N-ary Tree ✓
Explanation: A N-ary Tree is a tree data structure in which each node has a variable number of children, making it suitable for representing trees with nodes having variable number of children. Linked List, Stack, and Queue are not suitable for this purpose.
Q10. In a Binary Search Tree, what is the time complexity of searching for a node when the tree is self-balancing?
-
A. O(n)
-
B. O(log n) ✓
-
C. O(1)
-
D. O(n^2)
Explanation: A self-balancing Binary Search Tree, such as an AVL tree or a Red-Black tree, ensures that the height of the tree remains relatively small, even after insertions and deletions. This is achieved through rotations, which maintain the tree's balance factor. As a result, searching for a node in a self-balancing Binary Search Tree takes time proportional to the height of the tree, which is log(n) for a balanced tree with n nodes.
That was just a sample. Sign up to unlock the full question bank with timed tests and certificates.
Sign Up Free