# Construct a binary tree from given Inorder and Level Order Traversal

**Objective:** **– **Given a inorder and level order traversal, construct a binary tree from that.

**Input:** Inorder and level order traversal

**Approach:**

int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };

- First element in the
will be the*levelorder []**root*of the tree, here it is 1. - Now the search element 1 in
say you find it at position*inorder[]*,*i*, once you find it, make note of elements which are left to*i*(this will construct the) and elements which are right to**leftsubtree***i*( this will construct the).**rightSubtree** - Suppose in previous step, there are X number of elements which are left of ‘
*i’*(which will construct the leftsubtree), but these X elements will not be in the consecutive in levelorder[] so we will extract these elements fromby maintaining their sequence and store it in an array say*levelorder[]*.*newLeftLevel[]* - Similarly if there are Y number of elements which are right of ‘i’ (which will construct the rightsubtree), but these Y elements will not be in the consecutive in levelorder[] so we will extract these elements from
by maintaining their sequence and store it in an array say*levelorder[]**newRightLevel[]*. - From previous two steps construct the left and right subtree and link it to root.left and root.right respectively by making recursive calls using
and*newLeftLevel[]***newRightLevel[]**. - See the picture for better explanation.

**Complete Code:**

**Output**:

inorder traversal of constructed tree : 4 2 5 1 6 3 7

Great explanation! Thank you 🙂

Thanks Holden 🙂

Nicely explained. What is the time complexity of program?

Worst case it would be O(n^3) . extracting the elements in level order[] would be O(n^2) and one traversal for inorder[]. I will update the post. Thanks Jayesh.

I have one question. might be silly but would like to understand how Worst case time complexity would

be O(n^3)? what I am getting is O(n^2). one traversal for inorder[] doesn’t make it O(n^3).

Inorder traversal takes O(n) time and for each node traversal we are constructing new levelorder[] which takes O(n^2) time so total it takes O(n^3). Please correct me if I m wrong.

Any better algorithm available?