# Python short recursive solution.

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

• Hey caikehe, thank you for the great and clean code.

My code had MLE problem, and used the same algorithm as you. So I simplified my code using yours as model

My code ended up this (MLE):

``````if inorder:
node = TreeNode(preorder[0])
node_index = inorder.index(preorder[0])
l_len = len(inorder[:node_index])
node.left = self.buildTree(preorder[1:l_len+1], inorder[0:l_len])
node.right = self.buildTree(preorder[l_len+1:], inorder[l_len+1:])
return node
``````

but this worked (more similar like yours):

``````if inorder:
node = TreeNode(preorder[0])
node_index = inorder.index(preorder[0])
preorder.pop(0)
l_len = len(inorder[:node_index])
node.left = self.buildTree(preorder, inorder[0:l_len])
node.right = self.buildTree(preorder, inorder[l_len+1:])
return node
``````

I have been careful about the passing data in recursion, and usually encounter no problem in other questions.

Can you explain why I have to pass a popped "preorder", and cannot process "preorder" like "inorder"?

Thank you!

Answer: it is not a slicing error, it is because the slicing creates new lists, hence the space usage for preorder is doubled in each recursion

• The slice operation usually costs k space when you slice like list[:k], because you create a new list whose size is k. If you want to get rid of MLE, a normal way is using indexes, which means you can input the lower and upper bound indexes as parameters. For instance, the above example can call a helper function like: buildTreeHelper(preorder, inorder, lower1, upper1, lower2, upper2), lower1 and upper1, lower2 and upper2 are corresponding to the preorder and inorder indexes respectively.

• Preorder: [root, left nodes, right nodes],
Inorder: [left nodes, root, right nodes].
With preorder.pop(0) executed for each
node.left = self.buildTree(preorder[1:l_len+1], inorder[0:l_len]) and its recursive steps, we can guarantee that left nodes are all popped out in the preorder list and it is ready for
root.right = self.buildTree(preorder, inorder[ind+1:]).
That's why it works and it helps in avoiding building new sliced preorder list, but the better/clearer way to do it should be using a helper function like
buildTreeHelper(preorder, inorder, preLower, preUpper, inLower, inUpper)

• This post is deleted!

• Nice!!! How did you come up this idea?

• This is short as expected but it is slow because too many pop, slice and index operations.

• Slightly more optimal solution, but the index check makes this a slow solution. I'm sure there's a better solution without checking index of the inorder list

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

• @livelearn the inorder list doesn't have to be reversed, reversing the preorder list is enough.

• @skywalker_tju lol good point

• Looking at preorder traversal, the first value (node 1) must be the root.
Then, we find the index of root within in-order traversal, and split into two sub problems.

• @caikehe Beautiful solution! It took me a while to figure out that in your solution `left_preorder` and `right_preorder` are not being computed separately even though they could (to make the code more understandable). `preorder` is a mutable object (list) and since you are building the left-subtree first, it will just extract out it's elements first before the right subtree recursive call uses it. Just beautiful!

My solution (very similar to yours, only difference being that I explicitly computed the left_preorder and right_preorder lists before doing the recursive calls taking up more memory):

``````    def buildTree(self, preorder, inorder):

if len(inorder) == 0:
return None

if len(inorder) == 1:
return TreeNode(preorder[0])

rval = preorder[0]
root = TreeNode(rval)

inorder_rval_index = inorder.index(rval)
left_inorder = inorder[:inorder_rval_index]
right_inorder = inorder[inorder_rval_index+1:]
left_preorder = preorder[1: len(left_inorder) + 1]
right_preorder = preorder[1 + len(left_preorder):]

root.left = self.buildTree(left_preorder, left_inorder)
root.right = self.buildTree(right_preorder, right_inorder)

return root
``````

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