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

Step 1: Understanding the Question:
The question asks which tree traversal algorithm, when applied to a Binary Search Tree (BST), will visit the nodes in sorted (non-decreasing) order.
Step 2: Key Formula or Approach:
The defining property of a Binary Search Tree is that for any given node:

All values in its left subtree are less than or equal to the node's value.

All values in its right subtree are greater than or equal to the node's value.

Let's review the common traversal methods:

Preorder: Root \(\rightarrow\) Left \(\rightarrow\) Right

Inorder: Left \(\rightarrow\) Root \(\rightarrow\) Right

Postorder: Left \(\rightarrow\) Right \(\rightarrow\) Root

Step 3: Detailed Explanation:
By combining the BST property with the Inorder traversal algorithm, we can see why it produces a sorted list.
The Inorder traversal algorithm is defined as:
Recursively traverse the left subtree.
Visit the root node.
Recursively traverse the right subtree.
Following this on a BST, the algorithm first visits all the smaller elements (in the left subtree), then the current element (the root), and finally all the larger elements (in the right subtree). This process, when applied recursively down the tree, naturally results in visiting all nodes in ascending order.
Step 4: Final Answer:
The traversal method that produces elements in non-decreasing order in a BST is the Inorder Traversal.