## 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.

## Sample Test Case

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] 3 / \ 9 20 / \ 15 7

## Problem Solution

Preorder traversal starts at the root, goes to the left subtree and then to the right subtree. Inorder traversal starts at the left subtree, then goes through the root and then the right subtree.

So in order to construct a binary tree from preorder and inorder arrays, we can be sure that the root of the binary tree would be the same as the first element in the preorder array.

In order to construct the left subtree of this root, the next intuitive step is to locate this root node within the inorder array. Then in that case, all the node values to the left of that root node’s value would form it’s left subtree, while all the node values to the right of that root node’s value would form it’s right subtree.

Since solution to a larger problem (the entire tree) requires us to solve an incrementally smaller problem (the entire tree sans the previous level), recursion makes best intuitive sense to apply. With recursion, the foremost interest is to identify base conditions

Base conditions in this problem: ensure that start index of both the preorder and inorder arrays do not exceed the last index of the respective arrays; return null in either case.

With the base conditions in place, next the motive is to find the inIndex within the inorder array whose node value is equal to the root node’s value that corresponds to the current iterating index of the preorder array.

Once the inorder array index is found, recursive calls to construct the left subtree of this root node shall involve passing the (start, end) indexes of the inorder array as (inStart, inIndex — 1), in addition to the two arrays in question. Preorder array start index would simply be the next incremental value to the current preorder index.

Recursive calls to construct the right subtree of this root node shall involve passing the (start, end) indexes of the inorder array as (inIndex+1, inEnd), in addition to the two arrays in question. Preorder array start index would now be equal to the sum of current preorder index and the length of the left subtree, to account for the by now constructed left subtree.

At reach recursion, the root of the tree constructed is returned back to the calling function.

## Complexity Analysis

Time Complexity: In order to construct the entire tree, we end up visiting each node in both the arrays, so the time complexity is O(n).

Space Complexity: due to the stack space incurred due to recursion would amount to O(n).

## Code Implementation

#include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public: int data; node* left; node* right; }; /* Prototypes for utility functions */ int search(int arr[], int strt, int end, int value); node* newNode(int data); node* buildTree(int in[], int pre[], int inStrt, int inEnd) { static int preIndex = 0; if (inStrt > inEnd) return NULL; /* Pick current node from Preorder traversal using preIndex and increment preIndex */ node* tNode = newNode(pre[preIndex++]); /* If this node has no children then return */ if (inStrt == inEnd) return tNode; /* Else find the index of this node in Inorder traversal */ int inIndex = search(in, inStrt, inEnd, tNode->data); /* Using index in Inorder traversal, construct left and right subtress */ tNode->left = buildTree(in, pre, inStrt, inIndex - 1); tNode->right = buildTree(in, pre, inIndex + 1, inEnd); return tNode; } /* UTILITY FUNCTIONS */ /* Function to find index of value in arr[start...end] The function assumes that value is present in in[] */ int search(int arr[], int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) return i; } } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode(int data) { node* Node = new node(); Node->data = data; Node->left = NULL; Node->right = NULL; return (Node); } /* This funtcion is here just to test buildTree() */ void printInorder(node* node) { if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ cout<<node->data<<" "; /* now recur on right child */ printInorder(node->right); } /* Driver code */ int main() { int in[] = { 9,3,15,20,7 }; int pre[] = { 3,9,20,15,7 }; int len = sizeof(in) / sizeof(in[0]); node* root = buildTree(in, pre, 0, len - 1); /* Let us test the built tree by printing Insorder traversal */ cout << "Inorder traversal of the constructed tree is \n"; printInorder(root); }