101. Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

Problem

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

First Approach

My initial approach to this problem is to tackle the tree level by level (breadth-first search) and compare the nodes at each given level. A level is symmetrical if the nodes in the left half (from left to right) are the same and occur in the same order as the reverse of the nodes in the right half (from left to right).

By going level by level, if we find any level to be asymmetrical, then we can deduce that the tree is also asymmetrical. Once we reach the end of the tree without any hiccups, we can safely say that the tree is symmetrical.

def isSymmetric(root):
    # Edge Case: Tree is only 1 node
    if root:
        if not root.left:
            if not root.right:
                return True
    
    node = root
    queue = []
    
    level = 1  # Start from the second level
    numNodes = 2  # Second level has 2 nodes
    nodesAtLevel = []  # Stores the nodes on the given level
    
    while node:  # while node is not None
        if node.left:
            queue.append(node.left)
            nodesAtLevel.append(node.left.val)
        else:
            nodesAtLevel.append(None)
            
        if node.right:
            queue.append(node.right)
            nodesAtLevel.append(node.right.val)
        else:
            nodesAtLevel.append(None)

        if queue:
            node = queue.pop(0)
        else:
            break
        
        numNodes -= 2  # binary tree has 2 children
        
        if numNodes == 0:
            # If the current level is asymmetric
            half = len(nodesAtLevel)//2
            if nodesAtLevel[:half] != list(reversed(nodesAtLevel[half:])):
                return False
            
            # Else, proceed onto the next level
            level += 1
            numNodes = pow(2, level)
            nodesAtLevel = []
        
    return True

Mistake: symmetric around its center

For this question, symmetric around the center actually means given two nodes, their sub-trees are symmetric. For example:

          2
       /     \
      3       3
     / \     / \
    4   N   N   4
   / \ / \ / \ / \
  N   5   N   6   N

Revised Solution

Starting from scratch, we can still traverse the tree in a similar fashion with a variant of bread-first search / depth traversel. As we process two nodes as a time, we can picture an imaginary line that cuts in-between these two nodes as the CENTER of symmetry and its children are the left and right side (convenient since it's a binary).

    Node A    Node B
    /    \    /    \
   L1    R1  L2    R2

As such, we only need to compare two nodes at a time, and verify if the children on one side mirrors the other (reversed). The basic traversel algorithm therefore works as our starting base, and now we just filter two head nodes (Node A and Node B) and compare L1 == R2 and R1 == L2.

The Second Mistake

Had a huge slip-up here, forgetting a fundamental construct of binary search trees. The existence of None / Null. In the above section about my mistake, I erronously added children to the nodes which were None. However, this is impossible, as None cannot have any children - it simply stops there. By missing this slight error, this has caused me a huge headache and I realise now my original interpretation of the question was right - just that I was wrong. In the example given above, the tree actually should look like so:

          2
         / \
        3   3
       / \ / \
      4   N   4
     / \     / \
    N   5   5   N
       / \ / \
      N  6 6  N
        /\ /\
       7 8 8 7
      /\/\ /\/\
      9001 1009

How to know how many children to expect in the next level? Since each node is binary, the next level will have 2*(number of nodes in current level)

def isSymmetric(root):
    # Edge Case: Root is None
    if not root:
        return True

    # Edge Case: Root is only node in tree
    if not root.left:
        if not root.right:
            return True
    
    queue = [root]
    window = []
    
    num_nodes = 0
    expected_nodes = 2
    actual_nodes = 0
    
    while queue:
        curr = queue.pop(0)

        # Filter NoneType out
        if curr.left:
            queue.append(curr.left)
            window.append(curr.left.val)
            actual_nodes += 1
        else:
            window.append(None)

        # Apparently a normal check still allows NoneType through??
        if curr.right:
            queue.append(curr.right)
            window.append(curr.right.val)
            actual_nodes += 1
        else:
            window.append(None)

        num_nodes += 2
        if num_nodes == expected_nodes:
            # verify symmetry
            middle = len(window)//2
            if window[:middle] != list(reversed(window[middle:])):
                # print("ASYMMETRICAL:", window)
                return False            

            expected_nodes = actual_nodes*2  # calculate how many nodes we want in the next cycle
            num_nodes = 0
            actual_nodes = 0
            window = []

    return True