# Construct Binary Tree from Preorder and Inorder Traversal in Python

PythonServer Side ProgrammingProgramming

Suppose we have the inorder and preorder traversal sequence of a binary tree. We have to generate the tree from these sequences. So if the preorder and inorder sequences are [3,9,20,15,7] and [9,3,15,20,7], then the tree will be − Let us see the steps −

• Suppose the method is called buildTree with preorder and inorder lists
• root := first node from the preorder, and delete first node from preorder
• root_index := index of root.val from the inorder list
• left or root := buildTree(preorder, subset of inorder from 0 to root_index)
• right or root := buildTree(preorder, subset of inorder from root_index + 1 to end)

Let us see the following implementation to get better understanding −

## Example

Live Demo

class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
#print using inorder traversal
if root is not None:
print_tree(root.left)
print(root.data, end = ',')
print_tree(root.right)
class Solution(object):
def buildTree(self, preorder, inorder):
if inorder:
root = TreeNode(preorder.pop(0))
root_index = inorder.index(root.data)
root.left = self.buildTree(preorder,inorder[:root_index])
root.right = self.buildTree(preorder,inorder[root_index+1:])
return root
ob1 = Solution()
print_tree(ob1.buildTree([3,9,20,15,7], [9,3,15,20,7]))

## Input

[3,9,20,15,7]
[9,3,15,20,7]

## Output

9, 3, 15, 20, 7,
{"ft_lang_label":"__label__en","ft_lang_prob":0.51817614,"math_prob":0.97722375,"size":988,"snap":"2021-43-2021-49","text_gpt3_token_len":280,"char_repetition_ratio":0.14227642,"word_repetition_ratio":0.016260162,"special_character_ratio":0.3228745,"punctuation_ratio":0.27542374,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9936365,"pos_list":[0,1,2],"im_url_duplicate_count":[null,4,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-24T18:07:23Z\",\"WARC-Record-ID\":\"<urn:uuid:a14fe426-4a18-4e0b-a753-47a598b8a033>\",\"Content-Length\":\"32321\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:482884eb-00aa-4ba3-9571-587b15b42c3e>\",\"WARC-Concurrent-To\":\"<urn:uuid:560d9f89-c933-4924-9b9b-2320dcf9ab81>\",\"WARC-IP-Address\":\"72.21.91.42\",\"WARC-Target-URI\":\"https://www.tutorialspoint.com/construct-binary-tree-from-preorder-and-inorder-traversal-in-python\",\"WARC-Payload-Digest\":\"sha1:SEGHS3CRFY3UIBL4WHVW3WUVGP62YXYY\",\"WARC-Block-Digest\":\"sha1:GIIUUHDIMGSXQCPXHSKCCV7WK77KZGN5\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323587593.0_warc_CC-MAIN-20211024173743-20211024203743-00217.warc.gz\"}"}