BST (DS)

Question

17. The binary search tree contains the values—1, 2, 3, 4, 5, 6, 7 and 8. The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output?

(a) 5 3 1 2 4 7 8 6

(b) 5 3 1 2 6 4 8 7

(c) 5 3 2 4 1 6 7 8

(d) 5 3 1 2 4 7 6 8

Answer 1

From options we can conclude all are starting with node 5.so Root node is 5.

In preorder  visit Root first

                      then Left subtree and Right subtree

Root node is 5 and 2nd node is 3(from options).

 

From above tree preorder traversal is 5,3,1,2,4,7,6,8.

Hence Option D is correct.

Comments

WHY OTHER ONES ARE INVALID I AM ABLE TO CONSTRUCT BST USING THEM AND INORDER

---

consider

first option until 5,3,1,2,4,7,8.before insert 6 it occupies right node of 8 but it is not greater than 8.so false.

2nd option until 5,3,1,2,6.before insert 4 it occupies right node of 6.same reason as above.

3rd option.until 5,3,2,4.before 1 it occupies right of 4 so not greater.same reason as above.

---

THANKS :)