# A Python recursive solution

• The idea is to find the root first, and then recursively build each left and right subtree

Only Solution 3 could pass the OJ, but theoretically they should all work ...

Solution 1 - clean and easy to understand, but Memory Limit Exceeded ...

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

class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
# 1:59
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None

rootValue = preorder[0]
root = TreeNode(rootValue)
inorderIndex = inorder.index(rootValue)

root.left = self.buildTree(preorder[1:inorderIndex+1], inorder[:inorderIndex])
root.right = self.buildTree(preorder[inorderIndex+1:], inorder[inorderIndex+1:])

return root
``````

Solution 2 - Same as solution one, but pass index instead of doing list slicing (and thus reduce the memory usage)

``````class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
# 1:59
def buildTree(self, preorder, inorder, preorderStart = 0, preorderEnd = None, inorderStart = 0, inorderEnd = None):
if preorderEnd is None:
preorderEnd = len(preorder) - 1

if inorderEnd is None:
inorderEnd = len(inorder) - 1

if preorderStart > len(preorder) - 1 or inorderStart > inorderEnd:
return None

rootValue = preorder[preorderStart]
root = TreeNode(rootValue)
inorderIndex = inorder.index(rootValue)

root.left = self.buildTree(preorder, inorder, preorderStart+1, inorderIndex, inorderStart, inorderIndex-1)
root.right = self.buildTree(preorder, inorder, preorderStart+inorderIndex+1-inorderStart, preorderEnd, inorderIndex+1, inorderEnd)

return root
``````

Solution 3 - Based on Solution 1, we don't necessary need to slice the preorder array, when we are done with the left tree, the left half of the preorder array should already be empty

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

class Solution:
# @param preorder, a list of integers
# @param inorder, a list of integers
# @return a tree node
# 1:59
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None

rootValue = preorder.pop(0)
root = TreeNode(rootValue)
inorderIndex = inorder.index(rootValue)

root.left = self.buildTree(preorder, inorder[:inorderIndex])
root.right = self.buildTree(preorder, inorder[inorderIndex+1:])

return root``````

• why it says runtime error? It works fine on simple examples and should be working on large data sets too. hum....

• Well, I didn't really run the solution 2 in oj ... That's why I just added solution 3 :p

• And yes, I did run solution 3 in OJ and it passed lol

• The runtime error is because maximum recursion depth exceeded

• Simpler base-case-handling, `if inorder` is enough:

``````def buildTree(self, preorder, inorder):
if inorder:
root = TreeNode(preorder.pop(0))
inorderIndex = inorder.index(root.val)
root.left = self.buildTree(preorder, inorder[:inorderIndex])
root.right = self.buildTree(preorder, inorder[inorderIndex+1:])
return root
``````

Btw, what does the `1:59` mean? I've noticed I think `1:40` in another solution of yours before...

• pop(0) is O(n) so the complexity is n^2?

• Although solution 3 passes the system I still doubt that it consumes quite a lot of memory for always creating the latter half array. The optimal way for recursion should still be using indices.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.