[Math] Total number of possible order possible in this binary search tree

binarycombinatoricscomputer sciencediscrete mathematicspermutations

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$?

  1. $35$
  2. $64$
  3. $128$
  4. $5040$

My attempt:

This is previous question of GATE CS/IT. This question is explained somewhere as:
There are $4$ values that are smaller than $60$ and $3$ values are greater than $60$. We can rearrange in $4! = 24$ ways smaller values and rearrange $3! = 6$ ways.
Total number of different order are $= 7! /(4!*3!) = 35$ ways.

My argument is:

Same as : Number of binary search tree of height $6$

We can have $2^4$ number of sub-trees in left of root $60$ and $2^3$ number of sub-trees in right of root $60$ (in This case, both right subtree and left sub-tree will have skewed, that means linear).
So, total number of such trees $= 2^4 \times 2^3 = 2^7 = 128$

I am asking, what is flaw in my argument? Can you explain it, please?

Best Answer

A binary search tree has the property that, if a node contains value $v$, then all nodes to its left have values less than $v$, and all nodes to its right have values greater than $v$.

In this problem, a path containing all the listed values has been taken, from the root, to a node beneath it bearing the value $60$.

For each value $v$ appearing somewhere in the path, either:

  • all subsequent values appearing in the path must be greater than $v$, or
  • all subsequent values appearing in the path must be smaller than $v$.

The consequences are:

  • The first value must be either $10$ or $90$.
  • The next value, at any stage, must be either the smallest or greatest remaining in the list.

But the last value must be $60$. Therefore, values less than $60$ must be taken from the left-hand side, and values greater than $60$ must be taken from the right-hand side.

Therefore, the path can be represented by a permutation of the string $LLLLRRR$, and all such permutations can represent a valid path.

Related Question