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

Objective: Given an 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 };`
• The first element in the levelorder [] will be the root of the tree, here it is 1.
• Now the search ele­ment 1 in inorder[], say you find it at posi­tion i, once you find it, make note of ele­ments which are left to i (this will con­struct the left­sub­tree) and ele­ments which are right to i ( this will con­struct the rightSubtree).
• Suppose in the previous step, there is X number of elements which are left of ‘i’ (which will construct the left subtree), but these X elements will not be in the consecutive in levelorder[] so we will extract these elements from levelorder[] by maintaining their sequence and store it in an array say newLeftLevel[].
• Similarly, if there are Y number of elements which are right of ‘i’ (which will construct the right subtree), but these Y elements will not be in the consecutive in levelorder[] so we will extract these elements from levelorder[] by maintaining their sequence and store it in an array say newRightLevel[].
• From the previous two steps construct the left and right subtree and link it to root.left and root.right respectively by making recursive calls using newLeftLevel[] and newRightLevel[].
• See the picture for a better explanation.

Code:

Output:

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

### 7 thoughts on “Construct a binary tree from given Inorder and Level Order Traversal”

1. Great explanation! Thank you 🙂

• Thanks Holden 🙂

2. 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).

• 3.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8652517,"math_prob":0.9267902,"size":2245,"snap":"2022-27-2022-33","text_gpt3_token_len":554,"char_repetition_ratio":0.14993307,"word_repetition_ratio":0.14177215,"special_character_ratio":0.25122494,"punctuation_ratio":0.116071425,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9875565,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-14T07:33:07Z\",\"WARC-Record-ID\":\"<urn:uuid:7b922b8e-6030-45f9-98fe-64096fef9987>\",\"Content-Length\":\"101357\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:bb4732c9-10b6-400d-95d9-eb661dda09a5>\",\"WARC-Concurrent-To\":\"<urn:uuid:203238fb-e955-43fa-a0ce-74be3d7c8aee>\",\"WARC-IP-Address\":\"104.21.57.33\",\"WARC-Target-URI\":\"https://algorithms.tutorialhorizon.com/construct-a-binary-tree-from-given-inorder-and-level-order-traversal/?replytocom=5111\",\"WARC-Payload-Digest\":\"sha1:DYT33ZQHBGISG2DDAEYKJK2RDVL5YVTY\",\"WARC-Block-Digest\":\"sha1:27WPJIEZVRLCODLZAGP5XEP42QMG74NH\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882571996.63_warc_CC-MAIN-20220814052950-20220814082950-00422.warc.gz\"}"}