LevelOrderTraversal : Symmetric Tree

Iterative — Easy : https://leetcode.com/problems/symmetric-tree/

Recursive — Medium [ very important and intuitive]

Hint : 1. A Tree is symmetric to itself. So if you implement a function which accepts two trees to check for symmetry, you can start the first call of the function with symmetric(root, root).

Problem Statement:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

1
   / \
  2   2
   \   \
   3    3

Follow up: Solve it both recursively and iteratively.

Code:

Iterative:

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

Complexity Analysis

• Time complexity : O(n)O(n). Because we traverse the entire input tree once, the total run time is O(n)O(n), where nn is the total number of nodes in the tree.
• 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).

Recursive:

Approach 1: Recursive

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

Therefore, the question is: when are two trees a mirror reflection of each other?

Two trees are a mirror reflection of each other if:

1. Their two roots have the same value.
2. The right subtree of each tree is a mirror reflection of the left subtree of the other tree.

This is like a person looking at a mirror. The reflection in the mirror has the same head, but the reflection’s right arm corresponds to the actual person’s left arm, and vice versa.

The explanation above translates naturally to a recursive function as follows.

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)

Runtime: 32 ms, faster than 80.82% of Python3 online submissions for Symmetric Tree.

Memory Usage: 14.3 MB, less than 81.57% of Python3 online submissions forSymmetric Tree.

• Time complexity : O(n)O(n). Because we traverse the entire input tree once, the total run time is O(n)O(n), where nn is the total number of nodes in the tree.
• 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.

Next to Solve:

1. Number of Islands
2. Flatten a Multilevel Doubly Linked List
3. Cousins in Binary Tree