# LeetCode - Construct Binary Tree from Preorder and Inorder Traversal

## Problem statement

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.

Problem statement taken from: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

Example 1:

``````Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
``````

Example 2:

``````Input: preorder = [-1], inorder = [-1]
Output: [-1]
``````

Constraints:

``````- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder and inorder consist of unique values.
- Each value of inorder also appears in preorder.
- preorder is guaranteed to be the preorder traversal of the tree.
- inorder is guaranteed to be the inorder traversal of the tree.
``````

### Explanation

#### Brute force approach

The preorder sequence pattern is root-left-right and the inorder sequence is left-root-right. Node 3 in this preorder sequence [3, 9, 20, 15, 7] is the root. We search for node 3 in the inorder sequence. All the elements to the left of 3 in the inorder sequence belong to the left subtree and the elements to the right of it belong to the right subtree.

A C++ snippet of this approach is as follows:

``````TreeNode* buildTree(int inorder[], int preorder[], int inStart, int inEnd) {
static int preIndex = 0;

if (inStart > inEnd)
return NULL;

TreeNode* node = newNode(preorder[preIndex++]);

if (inStart == inEnd)
return node;

int inIndex = search(inorder, inStart, inEnd, node->data);

node->left = buildTree(inorder, preorder, inStart, inIndex - 1);
node->right = buildTree(inorder, preorder, inIndex + 1, inEnd);

return node;
}

int search(int arr[], int start, int end, char value) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == value)
return i;
}
}``````

The time complexity of this approach is O(n^2). The space complexity is O(n). The extra space is due to the recursive call stack.

#### Efficient solution: Using Map

We can optimize the search function by using hashing. We store the indexes of inorder sequence in a hash map.

A C++ snippet of this approach is as follows:

``````TreeNode* buildTree(int inorder[], int preorder[], int inStart, int inEnd, unordered_map<int, int>& mp) {
int preIndex = 0;

if (inStart > inEnd)
return NULL;

int current = preorder[preIndex++];
TreeNode* tNode = newNode(current);

if (inStart == inEnd)
return tNode;

int inIndex = mp[current];

tNode->left = buildTree(inorder, preorder, inStart, inIndex - 1, mp);
tNode->right = buildTree(inorder, preorder, inIndex + 1, inEnd, mp);

return tNode;
}``````

The time complexity of this approach is O(n). The space complexity is O(n). The extra space is used to store the elements in the map also due to the recursive function call stack.

#### Efficient solution: Using Stack

Instead of a map, we can also solve the problem using a stack and set. The stack will be used to store the path we traversed when iterating over the preorder array, and the set is used to maintain the node in which the next right subtree is expected.

Let's check the algorithm to understand it better.

#### Algorithm

``````- set TreeNode* root, node = NULL, NULL
create a set<TreeNode*> s
create a stack TreeNode* st
set n = preorder.size()

- loop for pre = 0, in = 0; pre < n
- set node = NULL

- loop do
- node = new TreeNode(preorder[pre])

- if root == NULL
- root = node
- if end

- if st.size() > 0
- if s.find(st.top()) != s.end()
- s.erase(st.top())
- st.top()->right = node
- st.pop()
- else
- st.top()->left = node
- if end
- if end

- st.push(node)
- while preorder[pre++] != inorder[in] && pre < n

- set node = NULL

- loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
- node = st.top()
- st.pop()
- in++
- while end

- if node != NULL
- s.insert(node)
- st.push(node)
- if end
- for end

- return root
``````

Let's check out our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* root = NULL;
TreeNode* node = NULL;
set<TreeNode*> s;
stack<TreeNode*> st;
int n = preorder.size();

for (int pre = 0, in = 0; pre < n;) {
node = NULL;
do {
node = new TreeNode(preorder[pre]);
if (root == NULL) {
root = node;
}

if (st.size() > 0) {
if (s.find(st.top()) != s.end()) {
s.erase(st.top());
st.top()->right = node;
st.pop();
} else {
st.top()->left = node;
}
}
st.push(node);
} while (preorder[pre++] != inorder[in] && pre < n);

node = NULL;

while(st.size() > 0 && in < n && st.top()->val == inorder[in]) {
node = st.top();
st.pop();
in++;
}

if(node != NULL) {
s.insert(node);
st.push(node);
}
}

return root;
}
};``````

#### Golang solution

We are using a map instead of a set here.

``````func buildTree(preorder []int, inorder []int) *TreeNode {
n := len(preorder)
if n == 0 {
return nil
} else if n == 1 {
return &TreeNode{Val: preorder[0]}
}

root := &TreeNode{Val: preorder[0]}
st := []*TreeNode{root}

m := make(map[int]int)
for i := 0; i < n; i++ {
m[inorder[i]] = i
}

var pop *TreeNode
for i := 1; i < n; i++ {
if m[preorder[i]] < m[st[len(st) - 1].Val] {
pop = st[len(st) - 1]
pop.Left = &TreeNode{Val: preorder[i]}
st = append(st, pop.Left)
continue
}

pop = st[len(st) - 1]
st = st[:len(st) - 1]

for len(st) > 0 && m[preorder[i]] > m[st[len(st)-1].Val] {
pop = st[len(st) - 1]
st = st[:len(st) - 1]
}

pop.Right = &TreeNode{Val: preorder[i]}
st = append(st, pop.Right)
}

return root
}``````

#### JavaScript solution

``````var buildTree = function(preorder, inorder) {
let set = new Set();
let stack = [];
let root = null;
let node = null;
let n = preorder.length;

for (let pre = 0, inOrder = 0; pre < n;) {
node = null;
do {
node = new TreeNode(preorder[pre]);
if (root == null) {
root = node;
}

if (stack.length != 0) {
if (set.has(stack[stack.length - 1])) {
set.delete(stack[stack.length - 1]);
stack.pop().right = node;
} else {
stack[stack.length - 1].left = node;
}
}

stack.push(node);
} while (preorder[pre++] != inorder[inOrder] && pre < preorder.length);

node = null;
while (stack.length != 0 && inOrder < n && stack[stack.length - 1].val == inorder[inOrder]) {
node = stack.pop();
inOrder++;
}

if (node != null) {
stack.push(node);
}
}

return root;
};``````

#### Dry Run

Let's dry-run our algorithm for a few examples to see how the solution works.

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

Step 1: TreeNode* root = NULL
TreeNode* node = NULL
set<TreeNode*> s
stack<TreeNode*> st
int n = preorder.size()
n = 5

Step 2: loop for pre = 0, in = 0; pre < n
0 < 5
true

loop do
node = new TreeNode(preorder[pre])
= new TreeNode(preorder[0])
= new TreeNode(3)

if root == NULL
true

root = node
= ->3

if st.size() > 0
0 > 0
false

st.push(node)
st.push(->3)

st = [3]

while preorder[pre++] != inorder[in] && pre < n
preorder[0] != inorder[0] && 1 < 5
3 != 9 && true
true

node = new TreeNode(preorder[pre])
= new TreeNode(preorder[1])
= new TreeNode(9)

if root == NULL
3 == NULL
false

if st.size() > 0
1 > 0
true

if s.find(st.top()) != s.end()
s = []
st.top = 3
s.find(st.top()) != s.end()
s.find(3) != s.end()
false
else
st.top()->left = node
3->left = 9
if end

st.push(node)
st.push(9)

st = [3, 9]

while preorder[pre++] != inorder[in] && pre < n
preorder[1] != inorder[0] && 2 < 5
9 != 9 && true
false
do end

node = NULL

loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
2 > 0 && 0 < 5 && st.top()->val == inorder[in]
true && true && 9 == inorder[0]
true && 9 == 9
true

node = st.top()
= 9

st.pop()
st = [3]

in++
in = 1

while st.size() > 0 && in < n && st.top()->val == inorder[in]
1 > 0 && 1 < 5 && 3 == inorder[1]
true && true && 3 == 3
true

node = st.top()
= 3

st.pop()
st = []

in++
in = 2

while st.size() > 0 && in < n && st.top()->val == inorder[in]
0 > 0 && 2 < 5
false
while end

if node != NULL
3 != NULL
true

s.insert(node)
s.insert(3)
s = [3]

st.push(node)
st.push(3)
st = [3]

Step 3: loop for pre < n
2 < 5
true

node = NULL

loop do
node = new TreeNode(preorder[pre])
= new TreeNode(preorder[2])
= new TreeNode(20)

if root == NULL
3 == NULL
false

if st.size() > 0
1 > 0
true

if s.find(st.top()) != s.end()
s = [3]
st.top() = 3
s.find(3) != s.end()
true

s.erase(st.top())
s.erase(3)
s = []

st.top()->right = node
3->right = 20
st.pop()
st = []

st.push(node)
st = [20]

while preorder[pre++] != inorder[in] && pre < n
preorder[2] != inorder[2] && 3 < 5
20 != 15 && true
true

node = new TreeNode(preorder[pre])
= new TreeNode(preorder[3])
= new TreeNode(15)

if root == NULL
3 == NULL
false

if st.size() > 0
1 > 0
true

if s.find(st.top()) != s.end()
s = []
st.top() = 20
s.find(20) != s.end()
false
else
st.top()->left = node
20->left = 15

st.push(node)
st = [20, 15]

while preorder[pre++] != inorder[in] && pre < n
preorder[3] != inorder[2] && 4 < 5
15 != 15 && true
false
do end

node = NULL

loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
2 > 0 && 2 < 5 && 15 == inorder[2]
true && 15 == 15

node = st.top()
= 15

st.pop()
st = [20]

in++
in = 3

loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
1 > 0 && 3 < 5 && 20 == inorder[3]
true && 20 == 20
true

node = st.top()
= 20

st.pop()
st = []

in++
in = 4

loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
0 > 0
false

if node != NULL
15 != NULL
true

s.insert(node)
s.insert(15)
s = [15]

st.push(node)
st.push(15)
st = [15]

Step 4: loop for pre < n
4 < 5
true

node = NULL

loop do
node = new TreeNode(preorder[pre])
= new TreeNode(preorder[4])
= new TreeNode(7)

if root == NULL
3 == NULL
false

if st.size() > 0
1 > 0
true

if s.find(st.top()) != s.end()
s = [15]
st.top() = 15
s.find(st.top()) != s.end()
true

s.erase(st.top())
s.erase(15)
s = []

st.top()->right = node
15->right = 7

st.pop()
st = []

st.push(node)
st = [7]

while preorder[pre++] != inorder[in] && pre < n
preorder[4] != inorder[4] && 5 < 5
7 != 7 && false
false

node = NULL

loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
1 > 0 && 4 < 5 && 7 == inorder[4]
true && 7 == 7
true

node = st.top()
= 7

st.pop()
st = []

in++
in = 5

loop while st.size() > 0 && in < n && st.top()->val == inorder[in]
0 > 0
false

if node != NULL
7 != NULL
true

s.insert(node)
s = [7]

st.push(node)
st = [7]

Step 5: loop for pre < n
5 < 5
false

Step 6: return root

We return the answer as [3, 9, 20, null, null, 15, 7].
``````