# 105 Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

... close

The idea: \*Pre order tells you what is the next root, while in order will tell you what the respected left and right subtrees are.

Consider:

```
        7
        10       2
          4   3      8
            1   11

Pre: 7, 10, 4, 3, 1, 2, 8, 11
In : 4, 10, 3, 1, 7, 11, 8, 2
```

* In the first instance, we know that the root will be 7. We identify 7 within the in order traversal, and discover that the left subtree must contain `4, 10, 3, 1,`, and right subtree `11, 8, 2` respectfully. Within the pre order traversal, we can also identify where this cut is. 
* So it then follows that every following node is the first element in the pre order traversal of its respected subtree, and its left and right subtree is said node identified within the in order traversal, split for a left and right hand side.
* The way this tree is constructed follows DFS, where for construct the nodes first, and only when we return do we link the pointers together.

```cpp
    Node<T> * buildTree_from_in_and_pre_order(vector<T> &in_order, vector<T> &pre_order) {
        Node<T> *root = buildTree_from_in_and_pre_order_rec
                        (in_order.begin(), in_order.end() - 1,
                        pre_order.begin(), pre_order.end() - 1);

        return root;
    }

    template<typename iter>
    Node<T>* buildTree_from_in_and_pre_order_rec(iter in_begin, iter in_end,
                                                 iter pre_begin, iter pre_end)
    {
        if (pre_begin >= pre_end || in_begin >= in_end)
            return nullptr;

        T next_root_i = *(pre_begin);

        // split next left and right subtrees
        iter new_left_in_strt, new_left_in_end;
        iter new_right_in_strt, new_right_in_end;

        for (iter it = in_begin; it != in_end + 1; it++) {
            if (*it == next_root_i) {
                new_left_in_strt = in_begin;
                new_left_in_end = it - 1;
                new_right_in_strt = it + 1;
                new_right_in_end = in_end;
                break;
            }
        }
        iter new_left_pre_strt, new_left_pre_end;
        iter new_right_pre_strt, new_right_pre_end;

        new_left_pre_strt = pre_begin + 1;
        new_left_pre_end = new_left_pre_strt + distance(new_left_in_strt, new_left_in_end);
        new_right_pre_strt = new_left_pre_end + 1;
        new_right_pre_end = pre_end;

        /*DEBUG PRINT*/
        cout << setw(11) << "left pre: " << *new_left_pre_strt << " " << *new_left_pre_end << endl;
        cout << setw(11) << "right pre: " << *new_right_pre_strt << " " << *new_right_pre_end << endl;
        cout << setw(11) << "left in: " << *new_left_in_strt << " " << *new_left_in_end << endl;
        cout << setw(11) << "right in: " << *new_right_in_strt << " " << *new_right_in_end << endl << endl;

        Node<T> *newRoot = new Node<T>(next_root_i);
        newRoot->left = buildTree_from_in_and_pre_order_rec(new_left_in_strt, new_left_in_end,
                                                            new_left_pre_strt, new_left_pre_end);
        newRoot->right = buildTree_from_in_and_pre_order_rec(new_right_in_strt, new_right_in_end,
                                                             new_right_pre_strt, new_right_pre_end);
        return newRoot;
    }
```


---

# 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/leetcode_sessions/105-construct-binary-tree-from-preorder-and-inorder-traversal.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.