# Maximum Depth of Binary Tree

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
i = 1
j = 0
while i < len(preorder)
# iterate through i, building tree
```

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

```def buildTree(preorder, inorder):
if len(preorder) == 0:
return None
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
```

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

Final Code

```def buildTree(preorder, inorder):
if len(preorder) == 0:
return None
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