LevelOrderTraversal : Symmetric Tree

1
/ \
2 2
/ \ / \
3 4 4 3
1
/ \
2 2
\ \
3 3
def isSymmetric(self, root: TreeNode) -> bool:
# seems like a level by level traversal, using a deque to store all children from left to right.
# we need to traverse the deque from front->mid and back->mid, at the same time and compare values at opposite end nodes.
# Also add the children of those nodes to the queue.
if not root or not (root.left or root.right):
return True

q = collections.deque()

if root.left and root.right:
q.append(root.left)
q.append(root.right)
else:
return False

while q:
length = len(q)

for i in range(length//2):
node = q[i]
mirrornode = q[length -1 -i]

# lets check the False conditions
if (node and not mirrornode) or (not node and mirrornode) or (node and mirrornode and node.val != mirrornode.val):
return False
break

for _ in range(length):
node = q.popleft()
if node:
q.append(node.left)
q.append(node.right)
i += 1

return True
  • Space complexity : There is additional space required for the search queue. In the worst case, we have to insert O(n)O(n) nodes in the queue. Therefore, space complexity is O(n)O(n).

Approach 1: Recursive

A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

  1. The right subtree of each tree is a mirror reflection of the left subtree of the other tree.
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:

def symmetric_subtrees(t1:TreeNode, t2:TreeNode) -> bool:
# both are None return True
if not t1 and not t2:
return True

# either one of them is True return False
if (t1 and not t2) or (not t1 and t2):
return False

# recursively check the right of the tree to equal the left of the 2nd tree
# and check the left of the tree to equal the right of the 2nd Tree
return t1.val == t2.val and symmetric_subtrees(t1.right, t2.left) and symmetric_subtrees(t1.left, t2.right)

# this is the mindboggling part of everything here.
return symmetric_subtrees(root, root)
  • Space complexity : The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear and the height is in O(n)O(n). Therefore, space complexity due to recursive calls on the stack is O(n)O(n) in the worst case.
  1. Flatten a Multilevel Doubly Linked List
  2. Cousins in Binary Tree

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store