The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the f

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2020 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2020 question covers Trees and Binary Trees topic.

Q: What is the difficulty level of this question?

This GATE-CS 2020 Data Structures question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

Accepted Answer

Correct Answer: (D) 11, 12, 10, 16, 19, 18, 20, 15Concept -- BST Reconstruction from Preorder Traversal: In preorder traversal, the first element is the root. For a BST, elements less than the root form the left subtree and elements greater form the right subtree. Preorder: 15, 10, 12, 11, 20, 18, 16, 19. Root = 15. Left subtree ( 15): 20, 18, 16, 19. Reconstruct: root=15; left subtree root=10, right of 10 is 12, left of 12 is 11; right subtree root=20, left of 20 is 18, left of 18 is 16, right of 18 is 19. BST structure: 15 (root), left child 10, right child of 10 is 12, left child of 12 is 11, right child of 15 is 20, left child of 20 is 18, left child of 18 is 16, right child of 18 is 19. Postorder (LRN): 11, 12, 10 (left subtree postorder), 16, 19, 18, 20 (right subtree postorder), 15. Full postorder: 11, 12, 10, 16, 19, 18, 20, 15.

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

Master GATE-CS with Our Test Series

More Questions from Trees and Binary Trees

Frequently Asked Questions

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

Master GATE-CS with Our Test Series

More Questions from Trees and Binary Trees

Frequently Asked Questions