Sources: leetcode 105

Rating: medium

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

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder: List[int], inorder: List[int]) -> TreeNode:
# give binary tree

**Solution**

Initialize the head of the tree based on the preorder list, then set up an interation using two indices, i for the preoder and j for the inorder list.

def buildTree(preorder, inorder):
if len(preorder) == 0:
return None
head = TreeNode(preorder[0])
stack = [head]
i = 1
j = 0
while i < len(preorder)
# iterate through i, building tree
return head

Use the stack to identify the next preorder and inorder node.

def buildTree(preorder, inorder):
if len(preorder) == 0:
return None
head = TreeNode(preorder[0])
stack = [head]
i = 1
j = 0
while i < len(preorder)
temp = None
t = TreeNode(preorder[i])
while stack and stack[-1].val == inorder[j]:
temp = stack.pop()
j += 1
# add children
return head

Finally, add the child nodes, extend the stack, and increment i.

**Final Code**

def buildTree(preorder, inorder):
if len(preorder) == 0:
return None
head = TreeNode(preorder[0])
stack = [head]
i = 1
j = 0
while i < len(preorder)
temp = None
t = TreeNode(preorder[i])
while stack and stack[-1].val == inorder[j]:
temp = stack.pop()
j += 1
if temp:
temp.right = t
else:
stack[-1].left = t
stack.append(t)
i += 1
return head

### Like this:

Like Loading...

*Related*