Attribute error in solving LeetCode challenge "Merge Two Binary Trees"

Question

I'm trying to solve LeetCode problem 617. Merge Two Binary Trees:

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

In order to execute it, I created a new tree and tried assigning the values of two nodes as value for the new node. But, I fail to assign a value for one of the child nodes in the binary tree.

This is my code:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def mergeTrees(self, root1, root2):
        if not root1 and not root2:
            return

        if root1 and root2:
            root3 = TreeNode(root1.val + root2.val)
            print(root3)
        elif root1:
            root3 = TreeNode(root1.val)
        elif root2:
            root3 = TreeNode(root2.val)

        root3.left = self.mergeTrees(root1.left, root2.left)
        root3.right = self.mergeTrees(root1.right, root2.right)

        return root3

# My driver code: create two trees and call above method
p = TreeNode(1)
p.left = TreeNode(2)
p.left.left = TreeNode(3)
p.left.right = TreeNode(4)
p.right = TreeNode(2)
p.right.left = TreeNode(4)
p.right.right = TreeNode(3)

q = TreeNode(1)
q.left = TreeNode(2)
q.left.left = TreeNode(4)
q.left.right = TreeNode(5)
q.left.left.left = TreeNode(8)
q.left.left.right = TreeNode(9)
q.right = TreeNode(3)
q.right.left = TreeNode(6)
q.right.right = TreeNode(7)

merged = Solution().mergeTrees(p, q)

The result I got:

AttributeError: 'NoneType' object has no attribute 'left'

What is my mistake?

Answer 1

The error occurs where you make the recursive call and pass as argument root1.left, but don't verify whether root1 is None. If root1 is None you get that error which correctly says that it has no attribute left.

The correction is simple: if root1 is None, just pass None as argument instead of root1.left. The same should be done for the second argument, and the second recursive call.

Correction:

    root3.left = self.mergeTrees(root1 and root1.left, root2 and root2.left)
    root3.right = self.mergeTrees(root1 and root1.right, root2 and root2.right)

Here we evaluate the expression root1 and root1.left. In case root1 is None it is a falsy value and so the expression evaluates to root1, i.e. None. In the case root1 is not None, the expression evaluates to the second operand of the and operation, i.e. to root1.left.

Remark

Unrelated, but you could gain some execution time by not creating new nodes, especially when arriving at a case where just one of the two trees still has a node at a given location. In that case you can stop the recursion and just return that node -- together with the subtree it might have below it.