Total number of possible order possible in this binary search tree?

Question

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?

Answer 1

You are counting something totally different from what the problem is talking about. It appears that you are counting how many binary search trees there are that have $60$ at the top such that both branches below $60$ are linear. But that's not at all what the binary search tree in the problem looks like. Instead, $60$ is at the bottom, and the entire binary search tree is linear.

(Incidentally, your count is also wrong for what you are counting. For instance, there are only $2^2$ linear binary search trees on $\{60,70,80,90\}$ that start with $60$. There are $2^3$ linear binary search trees on this set total, but half of them start with $90$ instead of $60$.)

Answer 2

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.