Test Series QS - Algorithms

Question

When searching for the key value 50 in a binary search tree, node containing the key values 10, 30, 40, 70, 90, 120, 150, 175 are traversed, in any order. The number of different orders passing in which these keys values can occur on the search path from the root to node containing the value 50 are ________.

Answer 1

left side of 50 contains 10,30,40  total 3 elements..

right side of 50 contains 70,90,120,150,175 total 5 elements..

so no of different passing from root to node is = 8!/(3! *5!) = 56.

Comments

Can you give a few orders in which all elements are traversed, while searching for 50? Or am I misinterpreting the question?

---

this qs asks how many ways u can reach 50.draw the bst  yourself..and u can reach to 50 node containing those given nodes in 56 ways.this is just a qs of combinatorics..just think that way..and the  ans is absolutely right.. :)

Answer 2

10,20,30  follows ascending order and 175,150,120,90,70 follows descending order in searching path. Therefore we fixed either of them. If we fix _10_20_30_  then there are four places to place 175..70 . Now this problem same like 'number of ball puts in number of boxes' .  Here #boxes = 4 and identical balls = 5 . Therefore n+r-1Cn-1 = 4+5-1C4-1= 56.
! Here 175.. 70 this number not permuted which they follows their order.
If any doubt then  place numbers and count.