Binary Search Tree Orders Possible


#1

When Searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed , not necessarily in the order given . How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60 ?

A. 35
B. 64
C. 128
D. 5040


#2

Given key values are : 10, 20, 40, 50, 70, 80, 90

Key values greater than 60: 70 80 90
Key values smaller than 60: 10 20 40 50

Now we have to arrange ‘10 20 40 50 70 80 90’ in such way that the relative ordering ’ 10 20 30 40’ and ’ 90 80 70 ’ are maintained.

= Total Permutations/Restricted permutations

= 7!/4!3!

= 35

So option A is correct.

An example of the tree that we counted:

10
  \
  90
  /
20
  \
  40
    \
    80
   /
  50
    \
    70
   /
  60

If you take the inorder traversal of the above tree then it will be in sorted ascending order (Property Of BST satisfied).


#5

so if the in order transversal of a tree is sorted does it guarantee that tree will be always Binary search tree ?


#6

Yes the tree will be BST always. This is how you check if a tree is BST or not also.


#7

Is it the most efficient to check BST


#8

If we are restricted to use the BST as a tree then yes it is the most efficient way to check for BST. But if we are allowed to scan through the array on which BST is implemented, then we can just have a linear search and determine if it’s a BST and not using constant memory space too.