[Trees and Graphs] interview questions #9

[rygh4775]

BST Sequences: A binary search tree was created by traversing through an array from left to right and inserting each element. Given a binary search tree with distinct elements, print all possible arrays that could have led to this tree.

[btakeya]

1. grouping by height
2. make combination by height from higher groups e.g. when a tree is given as below,

    7
   3     10
   1  5   8  12

   • h1: [7]
   • h2: [3, 10]
   • h3: [1, 5, 8, 12]

then,

1. make combination of [7] from h1 ([7])
2. append combination of [3, 10] from h2 ([7, 3, 10], [7, 10, 3])
3. append combination of [1, 5, 8, 12] from h3 ([7, 3, 10, 1, 5, 8, 12], [7, 3, 10, 1, 5, 12, 8], ...)
4. and goes on...

time complexity is O(h * 2^h) - to make combination of each level is O(2^h) and do it for each level h