Symmetric Binary Tree - Fill the symmetric stub

This article is part 3 of the series Symmetric Binary Tree

Suppose we are given two subtrees, root1 and root2, how can we check that they are symmetric?

First, if root1 and root2 are None we can definitely say that subtrees are symmetric.

Otherwise, we need to check:

Whether subtree of root1.left is symmetric to the subtree of root2.right
Whether subtree of root1.right is symmetric to the subtree of root2.left

test_symmetric

 def symmetric_roots(root1: Node,root2) -> bool:
     if root1 is None and root2 is None:
         return True
     # ... Add other condtions : return False when the nodes are not symmetric
     return symmetric_roots(root1.left,root2.right) and symmetric_roots(root1.right,root2.left)

Of course, we need to think when the subtrees are not symmetric and add those condtions to the recursive function.

The tree is not recursive if :

Only one of root1.left and root2.right is None
Only one of root1.right and root2.left is None
The data stored in root1.left and the data stored in root2.right are different
The data stored in root2.left and the data stored in root1.right are different

Let's add those condtions

symmetric_roots

 def symmetric_roots(root1: Node, root2) -> bool:
     if root1 is None and root2 is None:
         return True

     if not root1.left and root2.right or root1.left and not root2.right:
         return False

     if not root2.left and root1.right or root2.left and not root1.right:
         return False

     if root1.left and root2.right and root1.left.data != root2.right.data:
         return False

     if root2.left and root1.right and root2.left.data != root1.right.data:
         return False

     return symmetric_roots(root1.left, root2.right) and symmetric_roots(root1.right, root2.left)

Now we can easily check if binary is symmetric. Can you explain why?

symmetric

 def symmetric(root: Node) -> bool:
     return symmetric_roots(root,root)

The last thing we need to do is to run the tests

symmetric

 $ python -m unittest tests.symetric              
 .                                                                     ----------------------------------------------------------------------
 
 OK

Yes, we successfully solved the part 1 of the quiz.

Let's solve the part 2 of the quiz