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

Step 1: Build the tree by inserting 1, 2, 3, ... in order. Insert 1 as root. Insert 2: it is larger than 1, so it becomes the right child of 1. Insert 3: larger than 1, go right to 2, larger than 2, becomes right child of 2. Every next value is larger than all existing, so it keeps going right.

Step 2: The result is a right-skewed chain: 1 at the top, 2 below it on the right, then 3, and so on down to 10 at the bottom.

Step 3: Postorder is left, then right, then root. Every node has no left child, so postorder becomes: visit the right subtree, then the node.

Step 4: Starting at root 1, we must fully finish its right subtree before printing 1. That right subtree finishes with 2 only after its own right subtree, and so on. So the deepest node 10 prints first, then 9, then 8, down to 1 last.

Step 5: The postorder is \(10, 9, 8, 7, 6, 5, 4, 3, 2, 1\). The correct option is (B).