Friedrich Ewald My Personal Website

Leetcode: Symmetric tree

The task is to determine if a tree is symmetric, meaning mirrored along the root node. The usual tree structure is given in form of a TreeNode. 

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
A symmetric tree looks like this:
Note that the 3 and 4 are flipped in the left vs. right branch.

         1
       /   \
      2     2
     / \   / \
    3   4 4   3


An asymmetric tree looks like this:
Note that the 3 would need to be on the other side of 
either branch to make this tree symmetric.

         1
       /   \
      2     2
     /     /
    3     3
The logic itself is quite straightforward look at two nodes and compare the values. If their respective values are the same look at both of their children and compare them. Repeat this process until every node is visited. There are some special cases here that need to be handled. The left child can be None while the right child is not and vice versa. If both children are None, return True and do not proceed because this means we reached a leaf node. The recursive solution looks like this. 
class Solution:
  def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    if root is None:
      return True
    return self.inner(root.left, root.right)

  def inner(self, left, right) -> bool:
    if left is None and right is None:
      return True
    if left is None and right is not None:
      return False
    if left is not None and right is None:
      return False
    l = self.inner(left.left, right.right)
    r = self.inner(left.right, right.left)
    return left.val == right.val and l and r
And the iterative solution looks like this. 
class Solution:
  def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    if root is None:
      return True
    
    # Create stack and initialize with immediate successors
    stack = [(root.left, root.right)]
    
    while len(stack) > 0:
      n = stack[0]
      stack = stack[1:]
      if n[0] is None and n[1] is not None:
        return False
      if n[0] is not None and n[1] is None:
        return False
      if n[0] is None and n[1] is None:
        continue

      if n[0].val != n[1].val:
        return False
      stack.append((n[0].left, n[1].right))
      stack.append((n[0].right, n[1].left))

    return True
Test both solutions with the following code: 
if __name__ == '__main__':
  s = Solution().isSymmetric
  print(s(TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))), True)

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts