# Python, Straightforward with Explanation

• Let's create a recursive solution.

• If both trees are empty then we return empty.
• Otherwise, we will return a tree. The root value will be t1.val + t2.val, except these values are 0 if the tree is empty.
• The left child will be the merge of t1.left and t2.left, except these trees are empty if the parent is empty.
• The right child is similar.
``````def mergeTrees(self, t1, t2):
if not t1 and not t2: return None
ans = TreeNode((t1.val if t1 else 0) + (t2.val if t2 else 0))
ans.left = self.mergeTrees(t1 and t1.left, t2 and t2.left)
ans.right = self.mergeTrees(t1 and t1.right, t2 and t2.right)
return ans
``````

• I give u a big "LIKE"

• ans.left = self.mergeTrees(t1 and t1.left, t2 and t2.left)

I'm new to this game, how does "and" work? Could you briefly explain?

• @qxlin I am using `t1 and t1.left` as a shortcut for `t1.left if t1 is not None else None`.

Here, "`x and y`" evaluates as follows: If `x` is truthy, then the expression evaluates as `y`. Otherwise, it evaluates as `x`.

When `t1` is `None`, then `None` is falsy, and `t1 and t1.left` evaluates as `t1` which is `None`.

When `t1` is not `None`, then `t1` is truthy, and `t1 and t1.left` evaluates as `t1.left` as desired.

This is a standard type of idiom similar to the "?" operator in other languages. I want `t1.left` if `t1` exists, otherwise nothing.

Alternatively, I could use a more formal `getattr` operator: `getattr(t1, 'left', None)`

• @awice Thanks so much! I am familiar with '?' operator(or the if else statement), but python always surprises me!

• Thanks for nice explaination!

• Thanks for sharing a nice looking solution! I tried it and got 132 ms. I was surprised to see that it underperformed my initial naive implementation (125ms). I guess not creating a new TreeNode helps a bit if one of the sides is None:

``````def mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if not t1 and not t2:
return

if not t1:
res = t2
elif not t2:
res = t1
else:
res = TreeNode(t1.val+t2.val)
res.left = self.mergeTrees(t1.left,t2.left)
res.right = self.mergeTrees(t1.right,t2.right)

return res
``````

• Here is a complete analysis of this algorithm:
http://liqichen.com/daily-leetcode-in-python-merge-two-binary-tree/

• Thanks for sharing. I have a revised version of this and I think it is faster and easier to understand:

``````def mergeTrees(self, t1, t2):

if t1 and t2:
root = TreeNode(t1.val + t2.val)
root.left = self.mergeTrees(t1.left, t2.left)
root.right = self.mergeTrees(t1.right, t2.right)
return root
else:
return t1 or t2
``````

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