# Solution For Construct Binary Tree From Preorder And Inorder Traversal

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

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

Example:
Input:
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

Output:
3
/ \
9 20
/ \
15 7

Solution:
The strategy here is to use the first element of the preorder list to construct the root of the binary tree. Then, we use the root value to divide the inorder list into left and right subtrees. We then recursively construct the left and right subtrees using the remaining elements in the preorder list.

Steps:
1. Define the recursive function constructTree(preorder, inorder, in_start, in_end) that returns a constructed binary tree in that subtree in inorder from in_start to in_end.

1. First, check if the list is empty.
2. Define the root of the tree as the first element in the preorder list.
3. Find the position of the root value in the inorder list, which will help in dividing the inorder list into left and right subtrees.
4. Calculate the length of the left subtree using the position of the root value in the inorder list.
5. Construct the left subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the left subtree.
6. Construct the right subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the right subtree.
7. Return the root of the constructed binary tree.

Code:

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def constructTree(preorder, inorder, in_start, in_end):
if in_start > in_end:
return None

``````        root_val = preorder.pop(0)
root = TreeNode(root_val)

root_index_inorder = inorder.index(root_val)
length_left_subtree = root_index_inorder - in_start

root.left = constructTree(preorder, inorder, in_start, root_index_inorder - 1)
root.right = constructTree(preorder, inorder, root_index_inorder + 1, in_end)

return root

return constructTree(preorder, inorder, 0, len(inorder)-1)
``````

Time Complexity: O(n^2)
In the worst case, the function runs O(n) times, and each time it searches for the root value in the inorder list which takes O(n).

Space Complexity: O(n)
In the worst case, the function uses O(n) space to store the binary tree.

## Step by Step Implementation For Construct Binary Tree From Preorder And Inorder Traversal

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
//check for empty input
if(preorder.length == 0 || inorder.length == 0){
return null;
}

//initialize a hashmap for inorder traversal
HashMap map = new HashMap();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}

//call helper function
return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
}

public TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap map){
//base case
if(preStart > preEnd || inStart > inEnd){
return null;
}

//create the root node with the first element in the preorder traversal
TreeNode root = new TreeNode(preorder[preStart]);

//find the index of the root node in the inorder traversal
int inRoot = map.get(root.val);

//calculate the number of nodes in the left subtree
int numsLeft = inRoot - inStart;

//recursively build the left and right subtrees
root.left = helper(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, map);
root.right = helper(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, map);

return root;
}
}```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# if the list is empty, return None
if not preorder:
return None

# create a new TreeNode with the first element from preorder
root = TreeNode(preorder[0])

# find the index of the root in inorder
index = inorder.index(root.val)

# create the left and right subtrees
root.left = self.buildTree(preorder[1:index+1], inorder[:index])
root.right = self.buildTree(preorder[index+1:], inorder[index+1:])

return root```
```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
// base case
if (!preorder.length) return null;

// recursive case
let root = new TreeNode(preorder[0]);
let rootIndex = inorder.indexOf(preorder[0]);

root.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex));
root.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1));

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* buildTree(vector& preorder, vector& inorder) {

// Base case
if (preorder.size() == 0 || inorder.size() == 0)
return nullptr;

// The first element in preorder is always the root
TreeNode* root = new TreeNode(preorder[0]);

// Find the index of the root in inorder
int rootIdx;
for (int i = 0; i < inorder.size(); i++) {
if (inorder[i] == root->val) {
rootIdx = i;
break;
}
}

// Recursively build the left and right subtrees
vector leftInorder(inorder.begin(), inorder.begin() + rootIdx);
vector rightInorder(inorder.begin() + rootIdx + 1, inorder.end());
vector leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + rootIdx);
vector rightPreorder(preorder.begin() + 1 + rootIdx, preorder.end());

root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);

return root;
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
public class Solution {
public TreeNode BuildTree(int[] preorder, int[] inorder) {
// base case
if (preorder.Length == 0 || inorder.Length == 0) {
return null;
}

// create a hashmap of the inorder array elements for quick lookup
var inorderMap = new Dictionary();
for (int i = 0; i < inorder.Length; i++) {
}

// create the root node from the first element in the preorder array
TreeNode root = new TreeNode(preorder[0]);

// create a stack to keep track of nodes as we build the tree
Stack stack = new Stack();
stack.Push(root);

// create pointers for the preorder and inorder arrays
int preorderPointer = 1;
int inorderPointer = 0;

// iterate over the rest of the preorder array
while (preorderPointer < preorder.Length) {
// create a node from the next preorder array element
TreeNode node = new TreeNode(preorder[preorderPointer]);

// if the node's value is in the inorder array to the left of the current inorder pointer
// it is the left child of the node at the top of the stack
if (inorderMap[node.val] < inorderMap[stack.Peek().val]) {
stack.Peek().left = node;
}
// if the node's value is in the inorder array to the right of the current inorder pointer
// it is the right child of the node at the top of the stack
else {
// keep popping nodes off the stack until we find a node whose value is to the left of the current node's value
// in the inorder array
// when we find that node, the current node is its right child
TreeNode parent = null;
while (stack.Count > 0 && inorderMap[node.val] > inorderMap[stack.Peek().val]) {
parent = stack.Pop();
}
parent.right = node;
}

// push the current node onto the stack
stack.Push(node);

// increment the preorder and inorder pointers
preorderPointer++;
inorderPointer++;
}

return root;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]