Return to Answer

This runs in \$O(n)\$ time and \$O(d)\$ space, where \$d\$ is the depth of the tree. On a complete tree \$d\$ is \$\log n\$ but can be as bad as \$n\$.

This runs in \$O(n)\$ time and \$O(d)\$ space, where \$d\$ is the depth of the tree. This is because we make \$d\$ stack frames because we have used recursion. On a complete tree \$d\$ is \$\log n\$ but can be as bad as \$n\$ on a tree that is more line like.

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

This runs in \$O(n)\$ time and \$O(d)\$ space, where \$d\$ is the depth of the tree. On a complete tree \$d\$ is \$\log n\$ but can be as bad as \$n\$.

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.

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. To get a easier to understand stepping stone we can temporarally solve a different problem. Rather than checking if it's a mirror arround the root we just check the mirror around each node.

   Note: This is only to make this step easier to digest.

   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)),
   ))
   

6. We can now go back to solving the original problem. By swapping two grand-child nodes we can change the above to work down the middle of the tree.

   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
       if not _is_symmetric(node):
           return False
       if node.left is not None:
           (node.left.left, node.right.left) = (node.right.left, node.left.left)
       return 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(3)),
       Node(1, Node(3), Node(2)),
   ))
   assert not is_symmetric(Node(
       None,
       Node(1, Node(2), Node(3)),
       Node(1, Node(3), Node(1)),
   ))
   

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