Skip to main content

Construct Binary Tree from Preorder and Inorder Traversal


Given two arrays representing the preorder and inorder traversal of a binary tree, construct the binary tree.

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

/ \
9 20
/ \
15 7


all//Construct Binary Tree from Preorder and Inorder

# Definition for a binary tree node
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def buildTree(self, preorder, inorder):
if inorder:
# Find the index of the root node in the inorder list
idx = inorder.index(preorder.pop(0))
# Create the root node
root = TreeNode(inorder[idx])
# Recursively build the left and right subtrees
root.left = self.buildTree(preorder, inorder[0:idx])
root.right = self.buildTree(preorder, inorder[idx+1:])
return root