Recursive Algorithm to Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals pre and post are distinct positive integers.

Example 1:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:
1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, …, pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

How to Construct Binary Tree from Preorder and Postorder Traversal using C++ Recursion?

We know the root is the first element of the preorder. And we also know that it is also the last element of the post-order traversal. With that in mind, we need to find the left and right paritition of the preorder and the post order.

One way of doing it is to find the position of the first node in the left branch of the preorder – which is going to be the last element of the left branch of the post order.

For example, 1 is the root, and the first node in left branch of preorder is 2. We find 2 in the post order and partition it into [4, 5, 2] and [6, 7, 3]. So the parition of the preorder can go with [2, 4, 5] and [3, 6, 7] – the number of the nodes in preorder and postorder should be the same.

Presenting the recursive solution of constructing a binary tree in C++ from preorder and postorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        if (pre.empty()) return NULL;
        TreeNode* root = new TreeNode(pre[0]);
        if (pre.size() == 1) return root;
        int L = 0;
        for (int i = 0; i < post.size(); ++ i) {
            if (post[i] == pre[1]) {
                L = i + 1;
                break;
            }
        }
        vector<int> left1(begin(pre) + 1, begin(pre) + 1 + L);
        vector<int> right1(begin(post), begin(post) + L);
        vector<int> left2(begin(pre) + L + 1, end(pre));
        vector<int> right2(begin(post) + L, end(post) - 1);
        root->left = constructFromPrePost(left1, right1);
        root->right = constructFromPrePost(left2, right2);
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        if (pre.empty()) return NULL;
        TreeNode* root = new TreeNode(pre[0]);
        if (pre.size() == 1) return root;
        int L = 0;
        for (int i = 0; i < post.size(); ++ i) {
            if (post[i] == pre[1]) {
                L = i + 1;
                break;
            }
        }
        vector<int> left1(begin(pre) + 1, begin(pre) + 1 + L);
        vector<int> right1(begin(post), begin(post) + L);
        vector<int> left2(begin(pre) + L + 1, end(pre));
        vector<int> right2(begin(post) + L, end(post) - 1);
        root->left = constructFromPrePost(left1, right1);
        root->right = constructFromPrePost(left2, right2);
        return root;
    }
};

The runtime complexity is O(NlogN) when the tree is balance. e.g. T(N) = O(N) + 2*T(N/2) = O(NlgN). In the worst case when the tree is degrading into a linked list, the complexity is T(N) = O(N) + T(N – 1) = O(N ^ 2).

Related Binary Tree Construction Algorithms

You may also like the following posts on the similar tree problems.

• Recursive Algorithm to Construct Binary Tree from Preorder and Postorder Traversal
• How to Construct Binary Search Tree from Preorder Traversal in Python?
• Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
• How to Construct Binary Search Tree from Preorder Traversal? (C++ and Java)
• How to Construct String from Binary Tree?
• How to Balance a Binary Search Tree using Recursive Inorder Traversal Algorithm?
• How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?
• How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
• How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —