Question

The Postorder traversal of a Binary Search tree which is created by presenting the values in the order 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 will be:

• A. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• B. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
• C. 1, 10, 2, 9, 3, 8, 4, 7, 5, 6
• D. 1, 2, 3, 4, 5, 10, 9, 8, 7, 6

Hint:

An ascending insertion order makes a tree that leans fully to the right. In postorder, the root is printed last.

Answer 1

The Correct Option is B

Idea: Recognise the shape, then apply the postorder rule mechanically.

Inserting a strictly increasing sequence into a BST always produces a chain that leans entirely to the right. Node $k$ has node $k+1$ as its only (right) child.

Postorder prints a node only after its entire right subtree is done (there are no left children here):

\[\text{post}(k) = \text{post}(k+1),\; k\]

Unrolling from the root $k=1$ pushes every parent behind its child, so the printing order is bottom to top:

\[10,\,9,\,8,\,7,\,6,\,5,\,4,\,3,\,2,\,1\]

\[\boxed{10,\,9,\,8,\,7,\,6,\,5,\,4,\,3,\,2,\,1}\]