Recursion and Tree¶

Is tree symmetric¶

Screen Shot 2020-05-12 at 3.31.27 PM.png

Recurison Tree¶

Screen Shot 2020-05-12 at 3.32.11 PM.png

Solution¶

bool isSymmetric(left, right)
  if left == null and right == null
    return true
  else if left == null || right == null
    return false
  else if left.val != right.val
    return false
  else
    return isSymmetric(left.left, right.right) and isSymmetric(left.right, right.left)

Time = O(n/2)=O(n)

Calculate Time Complexity¶

Branch Factor: b Height: h

Total Complexity: $b^h$

Last update: January 9, 2021