You are given a set π of distinct integers. A binary search tree π isβ¦
2024
You are given a set π of distinct integers. A binary search tree π is created by inserting all elements of π one by one, starting with an empty tree. The tree π follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into π, and you do not have access to π.
Which one of the following statements is TRUE?
- A.
Inorder traversal of π can be determined from π
- B.
Root node of π can be determined from π
- C.
Preorder traversal of π can be determined from π
- D.
Postorder traversal of π can be determined from π
Attempted by 342 students.
Show answer & explanation
Correct answer: A
Key insight: inorder traversal of a binary search tree visits nodes in increasing order.
Reason:
Because every node's left subtree contains only smaller values and the right subtree only larger values, the inorder procedure (left, node, right) produces the elements in sorted (ascending) order.
Given the set V of distinct integers, sorting V gives the inorder traversal of T. This is independent of the insertion order.
Preorder, postorder and the choice of root depend on the insertion order (they depend on the tree shape), so they cannot be determined from V alone.
A video solution is available for this question β log in and enroll to watch it.