Binary search tree

Consider file system stores records as per binary search tree principles. If the postorder traversal of records is given by 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15. The expected number of comparisons when we randomly request one of the records (upto 2 decimal places) is _____.

gaurav singh @gaurav10022
9 Oct 2017 05:06 pm


suni @missiongate2018
9 Oct 2017 05:55 pm

How?? Please give complete solution


gaurav singh @gaurav10022
9 Oct 2017 06:19 pm

Firstly with the help of pre order given and since it's a binary search  tree so inorder traversal of this tree will be 2,3,4,6,7,9,13,15,17,18,20 .With the help of inorder and pre-order construct a binary search tree then at 0th height of tree there would be one comparison  and 1 element at 1 height 2 comparsion and 2 element at height 3,4 element and 3 comparisons and so on.. Now to calculate expected no of comparisons=1*1/n +2*2/n and so on