The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16,…

Concept: In a Binary Search Tree (BST), every node's left subtree holds only smaller keys and its right subtree only larger keys. Traversal orders differ purely in when the root is visited relative to its two subtrees: preorder visits root, then left subtree, then right subtree, while postorder visits left subtree, then right subtree, then root last. Because the BST ordering property is strict, a given preorder sequence reconstructs into exactly one tree, and a unique tree has exactly one postorder sequence.

1. The first value in the preorder sequence, 15, is the root (preorder always lists the root first).

2. Values smaller than 15 that follow form the left subtree: 10, 12, 11. Values larger than 15 form the right subtree: 20, 18, 16, 19.

3. Within the left subtree's preorder (10, 12, 11): 10 is the root of this subtree; 12 is larger than 10, so it becomes 10's right child; 11 is smaller than 12 but larger than 10, so it becomes the left child of 12.

4. Within the right subtree's preorder (20, 18, 16, 19): 20 is the root of this subtree; 18 is smaller than 20, so it becomes 20's left child; 16 is smaller than 18, so it becomes the left child of 18; 19 is larger than 18, so it becomes the right child of 18.

5. Postorder visits a node's left subtree, then its right subtree, then the node itself. For the subtree rooted at 10 (right child 12, whose left child is 11), the postorder is 11, 12, 10.

6. For the subtree rooted at 20 (left child 18, whose children are 16 on the left and 19 on the right), the postorder is 16, 19, 18, 20.

7. Combining left-subtree-postorder, right-subtree-postorder, and the overall root gives: 11, 12, 10, 16, 19, 18, 20, 15.

Cross-check: inserting the same values one at a time, in the given preorder sequence (15, 10, 12, 11, 20, 18, 16, 19), into an empty BST builds this identical structure — confirming the reconstruction, and its postorder is exactly 11, 12, 10, 16, 19, 18, 20, 15.