Return to Revisions

It would also be easier if we follow TDD - Test Driven Development.

1. We build the boiler plate that LeetCode is building for you.

   from __future__ import annotations
   
   import dataclasses
   from typing import Any, Optional
   
   
   @dataclasses.dataclass
   class Node:
       val: Any
       left: Optional[Node] = None
       right: Optional[Node] = None
   

2. We get a tree with only one node working. From this we can expand on the tests and code to get more working.

   This is simple we just check if both left and right are None.

   def is_symmetric(node):
       return node.left is None and node.right is None
   
   
   assert is_symmetric(Node(None))
   

3. We get a tree with 3 nodes working.

   The simplest way to do this is to just check if left and right's value are the same ignoring if either are None.

   def is_symmetric(node):
       return (
           (node.left is None and node.right is None)
           or (node.left.val == node.right.val)
       )
   
   
   assert is_symmetric(Node(None))
   assert is_symmetric(Node(None, Node(1), Node(1)))
   assert not is_symmetric(Node(None, Node(1), Node(2)))
   

4. We get a tree of size 1, 2 and 3 working.

   This makes the code a little more complicated as we now have to handle None for both left and right.

   def is_symmetric(node):
       if node.left is None:
           return node.right is None
       if node.right is None:
           return False
       return node.left.val == node.right.val
   
   
   assert is_symmetric(Node(None))
   assert is_symmetric(Node(None, Node(1), Node(1)))
   assert not is_symmetric(Node(None, Node(1), Node(2)))
   assert not is_symmetric(Node(None, left=Node(1)))
   assert not is_symmetric(Node(None, right=Node(1)))
   

5. We get a tree of size n working.

   Since we already have a function to check if a node is symmetric we can just call that to check if each of left and right are symmetric. This is called recursion.

   To return True the current is_symmetric needs to be true, and both the left and right have to be symmetric.

   To make the code a little easier to read we can:

   1. Move the current code into another function.
   2. Add a condition to return True if node is None.

   def _is_symmetric(node):
       if node.left is None:
           return node.right is None
       if node.right is None:
           return False
       return node.left.val == node.right.val
   
   
   def is_symmetric(node):
       if node is None:
           return True
       return _is_symmetric(node) and is_symmetric(node.left) and is_symmetric(node.right)
   
   
   assert is_symmetric(Node(None))
   assert is_symmetric(Node(None, Node(1), Node(1)))
   assert not is_symmetric(Node(None, Node(1), Node(2)))
   assert not is_symmetric(Node(None, left=Node(1)))
   assert not is_symmetric(Node(None, right=Node(1)))
   
   assert is_symmetric(None)
   assert is_symmetric(Node(
       None,
       Node(1, Node(2), Node(2)),
       Node(1, Node(3), Node(3)),
   ))
   assert not is_symmetric(Node(
       None,
       Node(1, Node(2), Node(1)),
       Node(1, Node(3), Node(3)),
   ))
   

This runs in \$O(n)\$ time and \$O(\log n)\$ space.