GATE Overflow Test Series | Mock GATE | Test 3 | Question: 42

Question

The preorder traversal sequence of a binary search tree is $12 , 4 , 2 , 1 , 3 , 8 , 6 , 10 , 17 , 15 , 14 , 16 , 19 , 18 , 20$. If the sum of the value of nodes whose index values (position from beginning) of preorder and postorder traversals are same is $k,$ then the value of $k$ is _________

Answer 1

The tree formed will be


$1 \quad 2  \quad   3 \quad   4 \quad    5 \quad   6 \quad   7 \quad    8 \quad   9 \quad  10 \quad  11 \quad  12 \quad 13 \quad 14 \quad 15$

The preorder sequence is $12 , 4 , 2 , 1 , 3 , 8 , 6 , 10 , 17 , 15 , 14 , 16 , 19 , 18 , 20$

The postorder sequence is $1 , 3 , 2 , 6 , 10 , 8 , 4 , 14 , 16 , 15 , 18 , 20 , 19 , 17 , 12$

We can clearly see that at index $3,6,10,13$ the values are same so the sum will be $k = 2 + 8 + 15 + 19 = 44.$

Comments

Is there any general method/ formula that can tell us which nodes will have the same position in post-order and pre-order traversal, for any given tree ..

---

how u directly made the tree??

any way