Given preorder and inorder traversal of a tree, construct the binary tree. You may assume that duplicates do not exist in the tree.
For example, given
1 2 preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Return the following binary tree:
3 / \ 9 20 / \ 15 7
How to Construct the Binary Tree using Divide-and-Conquer Algorithm?
The root element is located the first in a binary tree’s preorder. Thus, we can iterate the inorder to find the index of the root element, then, we know the left and right part of the inorder traversal. Then, going back to the preorder, we can also find the separation between left and right tree. Recursively, we can construct the left and right tree.
However, a first naive implementation is as follows C++, which is inefficient as the intermediate vectors are copied. And we have done some clumbsy work (remembering the left tree in the hash set) to find the separation point.
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty() || inorder.empty()) return nullptr; int n = preorder.size(); // root is the first element of preorder TreeNode* root = new TreeNode(preorder[0]); // push elements to set before root in inorder int i = 0; unordered_set<int> inorder_left_set; vector<int> inorder_left; while (i < n) { if (inorder[i] == root->val) break; inorder_left_set.insert(inorder[i]); inorder_left.push_back(inorder[i]); i ++; } // and the right part of the inorder vector<int> inorder_right; while (i < n) { inorder_right.push_back(inorder[i]); i ++; } // now push all nodes in set to preorder left int j = 1; vector<int> preorder_left; while (j < n) { if (!inorder_left_set.count(preorder[j])) break; preorder_left.push_back(preorder[j]); j ++; } // the right tree of the preorder vector<int> preorder_right; while (j < n) { preorder_right.push_back(preorder[j]); j ++; } // recursively construct left tree root->left = buildTree(preorder_left, inorder_left); // recursively construct right tree root->right = buildTree(preorder_right, inorder_right); return root; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty() || inorder.empty()) return nullptr; int n = preorder.size(); // root is the first element of preorder TreeNode* root = new TreeNode(preorder[0]); // push elements to set before root in inorder int i = 0; unordered_set<int> inorder_left_set; vector<int> inorder_left; while (i < n) { if (inorder[i] == root->val) break; inorder_left_set.insert(inorder[i]); inorder_left.push_back(inorder[i]); i ++; } // and the right part of the inorder vector<int> inorder_right; while (i < n) { inorder_right.push_back(inorder[i]); i ++; } // now push all nodes in set to preorder left int j = 1; vector<int> preorder_left; while (j < n) { if (!inorder_left_set.count(preorder[j])) break; preorder_left.push_back(preorder[j]); j ++; } // the right tree of the preorder vector<int> preorder_right; while (j < n) { preorder_right.push_back(preorder[j]); j ++; } // recursively construct left tree root->left = buildTree(preorder_left, inorder_left); // recursively construct right tree root->right = buildTree(preorder_right, inorder_right); return root; } };
A better implementation is as follows, based on the same algorithm. We define a helper function take takes 4 extra integer parameters to define the ranges of the traversal vectors – thus avoiding copying the vectors. Also, after finding the index of the root element in the inorder traversal, we can compute the number of nodes in the left tree, thus a quicker way to find the separation in the preorder 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 34 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } private: TreeNode* buildTree(vector<int>& preorder, int a, int b, vector<int>& inorder, int c, int d) { if (a > b) return nullptr; // root is the first element of preorder TreeNode* root = new TreeNode(preorder[a]); // find the root position in inorder int i = c; while (i <= d) { if (inorder[i] == root->val) break; i ++; } int leftcnt = i - c - 1; a ++; // recursively construct left tree root->left = buildTree(preorder, a, a + leftcnt, inorder, c, c + leftcnt); // recursively construct right tree root->right = buildTree(preorder, a + leftcnt + 1, b, inorder, i + 1, d); return root; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } private: TreeNode* buildTree(vector<int>& preorder, int a, int b, vector<int>& inorder, int c, int d) { if (a > b) return nullptr; // root is the first element of preorder TreeNode* root = new TreeNode(preorder[a]); // find the root position in inorder int i = c; while (i <= d) { if (inorder[i] == root->val) break; i ++; } int leftcnt = i - c - 1; a ++; // recursively construct left tree root->left = buildTree(preorder, a, a + leftcnt, inorder, c, c + leftcnt); // recursively construct right tree root->right = buildTree(preorder, a + leftcnt + 1, b, inorder, i + 1, d); return root; } };
The time complexity is O(N) where N nodes will be visited once during the process of constructing the binary tree. You can also use the similar algorithm to convert to a binary tree from its’ postorder and inorder sequences: How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
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) —
loading...
Last Post: The 24 Game Algorithm using Depth First Search
Next Post: How to Generate Parentheses using Bruteforce or Depth First Search (Backtracking) Algorithms?