# BST Sequences

**4.9 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.

Ex.\
![](http://i.imgur.com/3bkMzdC.png)

`Output: {2, 1, 3}, {2, 3, 1}`

* Brain storm:
  * I first noticed that a pre order traversal nicely prints out a possible combination of the array. I can use this transversal once, and use the output array as the basis of the remainder of my combinations depending on a few properties.
  * I will have a level order traversal, which will check to see if has another sibling (same parent), by using the property of B-trees that children with siblings are expected to grow by 2^n in pairs of two per level. In a binary configuration, this will determine whether the number is flippable in the combination.
    * num unique flips = log\_2(num flippables)
    * Each unique flip can be expressed as a combination on the number of states
      * num combination states = 2^(unique flip), an even number
  * In my pre-order tranversal array, each unique flip occurs with the next proceeding flip, and this will produce another combination based on the pre order combination.
  * Then, using each uniquely flipped array, we can write as a combination of the others, discluding itself and the preorder combination.
  * BigO: 
    * Preorder traversal O(N)
    * Parent check O(2N)

```cpp
vector<int> sameParentLevelTrav(Node *root) {
    vector<int> siblings;
    queue<Node *> q;
    Node *temp = new Node();
    q.push(root);

    int completeTreeCounter = 1;

    while (!q.isEmpty()) {
        temp = q.front();
        q.pop();

        // complete tree - siblings exist
        if (temp->left != null and temp->right != null) {
            siblings.push(temp->left->value);
            siblings.push(temp->right->value);
        }

        if (temp->left != null) {
            q.push(temp->left);
        }

        if (temp->right != null) {
            q.push(temp->right);
        }
    }
}

vector<int> preOrder(Node *root) {
    // assumming vector<int> preOrderNums is accessable in the class
    if (root != nullptr) {
        preOrderNums.push_back(root->value);
        preOrder(root->left);
        preOrder(root->right);
    }
    return preOrderNums;
}

vector<int> uniqueSwap(int one, int two, vector<int> &base) {

}

vector<vector<int>> BSTcombinations(Node *root) {
    vector<vector<int>> finalComb;

    // preorder array
    vector<int> preArr = preOrder(root);
    finalComb.push_back(preArr);

    // analyize siblings
    vector<int> siblings = sameParentLevelTrav(root);
    vector<int> temp = preArr;

    // find unique combinations
    int swap1_i = 0;
    int swap2_i = 1;
    while (swap2_i > siblings.size()) {

        int swap1 = siblings.at(swap1_i);
        int swap2 = siblings.at(swap2_i);

        // find where index exists
        int j;
        for (j = 0; j < temp.size(); j++) {
            if (temp.at(j) == swap1) {
                break;
            }
        }

        // find where index exists
        int k;
        for (k = 0; k < temp.size(); k++) {
            if (temp.at(k) == swap2) {
                break;
            }
        }

        // preform swap -> iter_swap <algorithm>
        iter_swap(temp.begin() + j, temp.begin() + k);
        finalComb.push_back(temp);

        // next iteration
        temp = preArr;
        swap1_i += 2;
        swap2_i += 2;
    }

    // find remaining combinations
    for (int i = 0; i < pow(2, finalComb.size() - 1); i++) {

    }
}
```

More efficient and complete implementation

```cpp
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions/bst-sequences.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.