Question

Which traversal of a binary tree gives the nodes in non-decreasing order if the tree is a Binary Search Tree?

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

Hint:

Remember: In-order traversal of a Binary Search Tree always gives a sorted list of node values in ascending order.

Answer 1

The Correct Option is B

In a Binary Search Tree (BST), the left subtree of any node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.
In-order traversal follows the sequence:
Left subtree → Root → Right subtree.
Applying this traversal on a BST visits the nodes in ascending (non-decreasing) order.
Let’s see why other options are incorrect:
(A) Pre-order (Root → Left → Right): This visits the root before the left subtree, so it doesn't preserve the sorted order.
(C) Post-order (Left → Right → Root): The root is visited last, so again, order is not preserved.
(D) Level-order (level by level): Depends on tree structure and doesn't guarantee sorted order.
Only (B) In-order traversal ensures sorted (non-decreasing) output for a BST.