Question

In a Binary Search Tree, which traversal method produces the elements in non-decreasing order?

• A. Preorder Traversal
• B. Inorder Traversal
• C. Postorder Traversal
• D. Level Order Traversal

Hint:

For any {Binary Search Tree}, performing an {Inorder Traversal} always returns the elements in {sorted order}.

Answer 1

The Correct Option is B

Concept: A Binary Search Tree (BST) is a special type of binary tree that satisfies the following property:

• All elements in the left subtree are smaller than the root.
• All elements in the right subtree are greater than the root.
• Both left and right subtrees are also Binary Search Trees.

Because of this property, performing an Inorder Traversal on a BST visits nodes in sorted (non-decreasing) order.
Step 1: Understand Inorder Traversal.
Inorder traversal follows the sequence: \[ \text{Left Subtree} \rightarrow \text{Root} \rightarrow \text{Right Subtree} \]
Step 2: Apply BST property.
Since:

• Left subtree contains smaller elements
• Root is the next element
• Right subtree contains larger elements

Visiting nodes in this order naturally produces a sorted sequence.
Step 3: Example.
Consider the following BST: \[ \begin{array}{c} 5
/
3 \ \ 7
/ \ \ /
2 \ 4 \ 6 \ 8 \end{array} \] Applying Inorder Traversal: \[ 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \] This sequence is in non-decreasing (sorted) order.
Step 4: Conclusion.
Therefore, the traversal that produces elements in sorted order in a Binary Search Tree is: \[ \text{Inorder Traversal} \]