# C++ recursive DFS template for constructing binary tree

• Construct Binary Tree from Preorder and Inorder Traversal

``````class Solution {
public:
unordered_map<int, int> um; // map inorder[i] to i
TreeNode* dfs(vector<int>& preorder, int pleft, int pright, vector<int>& inorder, int ileft, int iright) {
if(pleft > pright || ileft > iright) return nullptr;
int root_val = preorder[pleft]; // leftmost element in preorder is the root node
TreeNode* root = new TreeNode(root_val);

int root_idx = um[root_val]; // root index in inorder
int nleft = root_idx - ileft; // size of left sub-tree
root->left = dfs(preorder, pleft+1, pleft + nleft, inorder, ileft, root_idx - 1);
root->right = dfs(preorder, pleft + nleft + 1, pright, inorder, root_idx + 1, iright);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size(), i = 0;
for(int val : inorder) um[val] = i ++;
return dfs(preorder, 0, n-1, inorder, 0, n-1);
}
};
``````

Construct Binary Tree from Inorder and Postorder Traversal

``````class Solution {
public:
unordered_map<int, int> um; // map inorder[i] to i
TreeNode* dfs(vector<int>& inorder, int ileft, int iright, vector<int>& postorder, int pleft, int pright) {
if(ileft > iright || pleft > pright) return nullptr;
int root_val = postorder[pright]; // last element in postorder is the root node
TreeNode* root = new TreeNode(root_val);

int root_idx = um[val]; // root index in inorder
int nleft = root_idx - ileft; // size of left sub-tree
root->left = dfs(inorder, ileft, root_idx-1, postorder, pleft, pleft + nleft - 1);
root->right = dfs(inorder, root_idx+1, iright, postorder, pleft + nleft, pright - 1);
return root;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size(), i = 0;
for(int val : inorder) um[val] = i++;
return dfs(inorder, 0, n-1, postorder, 0, n-1);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.