GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes
The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____________ Note: The height of a tree with a single node is 0.
asked in trees, binary search trees, binary heaps by gate

1 Answer

0 votes

To get height 6, we need to put either 1 or 7 at root. So count can be written as T(n) = 2*T(n-1) with T(1) = 1

    7
   / 
 [1..6]  

    1
      \
     [2..7] 

Therefore count is 26 = 64

answered by gate
Only 1234567 or 7654321 are possible right?if we give any other order then height will become less than 6

Related questions

The best answer to any question