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.

    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;
    }