Question

Which binary search tree traversal gives the sorted order of its elements?

• A. Level order
• B. Pre-order
• C. Post-order
• D. In-order

Hint:

For a Binary Search Tree: In-order Traversal \(=\) Sorted Sequence

Answer 1

The Correct Option is D

Concept: A Binary Search Tree (BST) satisfies the property: \[ \text{Left Subtree} < \text{Root} < \text{Right Subtree} \] for every node. Tree traversal methods include:
• Pre-order
• In-order
• Post-order
• Level-order Among these, in-order traversal produces the elements in sorted order.

Step 1: Recall In-order traversal.
In-order traversal follows: \[ \text{Left} \rightarrow \text{Root} \rightarrow \text{Right} \]

Step 2: Apply BST property.
Since every left child contains smaller values and every right child contains larger values, visiting: \[ \text{Left} \rightarrow \text{Root} \rightarrow \text{Right} \] automatically generates elements in ascending order.

Step 3: Illustration.
Consider: \[ \begin{array}{c} 20 / \ \backslash 10 \ \ 30 \end{array} \] In-order traversal gives: \[ 10,20,30 \] which is sorted.

Step 4: Write the answer.
Therefore, \[ \boxed{\text{In-order Traversal}} \] gives sorted order. Hence option (D) is correct.