Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order…
2025
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
- A.
7 5 1 0 3 2 4 6 8 9
- B.
0 2 4 3 1 6 5 9 8 7
- C.
0 1 2 3 4 5 6 7 8 9
- D.
9 8 6 4 2 3 0 1 5 7
Attempted by 209 students.
Show answer & explanation
Correct answer: C
Explanation:
To find the in-order traversal, we first insert the numbers in the given order into a binary search tree (BST). The BST property ensures that for any node, all values in the left subtree are smaller and all values in the right subtree are larger.
Insertion order: 7, 5, 1, 8, 3, 6, 0, 9, 4, 2.
Step-by-step insertion:
1. Insert 7: Root node.
2. Insert 5: 5 < 7 → left child of 7.
3. Insert 1: 1 < 7, 1 < 5 → left child of 5.
4. Insert 8: 8 > 7 → right child of 7.
5. Insert 3: 3 < 7, 3 < 5 → left child of 5. 3 > 1 → right child of 1.
6. Insert 6: 6 > 7 → no, 6 > 5 → right child of 5.
7. Insert 0: 0 < 7, 0 < 5, 0 < 1 → left child of 1.
8. Insert 9: 9 > 7, 9 > 8 → right child of 8.
9. Insert 4: 4 < 7, 4 < 5, 4 > 1, 4 > 3 → right child of 3.
10. Insert 2: 2 < 7, 2 < 5, 2 > 1, 2 < 3 → left child of 3.
In-order traversal visits nodes in the order: left subtree, root, right subtree. This results in the sequence: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Thus, the in-order traversal is 0 1 2 3 4 5 6 7 8 9.
हिन्दी उत्तर:
स्पष्टीकरण: बाइनरी सर्च ट्री (BST) का इन-ऑर्डर ट्रैवर्सल तत्वों को बढ़ते क्रम में देता है। दिए गए संख्याओं को दिए गए क्रम में BST में डालने पर, इन-ऑर्डर ट्रैवर्सल 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 होगा।