# Cousins in Binary Tree
# In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

# Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

# We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

# Return true if and only if the nodes corresponding to the values x and y are cousins.

# Example 1:
# Input: root = [1, 2, 3, 4], x = 4, y = 3
# Output: false

# Example 2:
# Input: root = [1, 2, 3, null, 4, null, 5], x = 5, y = 4
# Output: true

# Example 3:
# Input: root = [1, 2, 3, null, 4], x = 2, y = 3
# Output: false


# Constraints:

# The number of nodes in the tree will be between 2 and 100.
# Each node has a unique integer value from 1 to 100.

# Definition for a binary tree node.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:

        if not root:
            return

        if x == y:
            return True

        q = []
        q.append(root)
        q.append("#")
        parent_x = parent_y = None

        while q:
            node = q.pop(0)
            if node == "#":
                if not q:  # marks the completion of a Tree
                    break
                else:
                    q.append("#")
                    parent_x = parent_y = None
                    continue
            if node.left:
                if node.left.val == x:
                    parent_x = node
                if node.left.val == y:
                    parent_y = node
                q.append(node.left)
            if node.right:
                if node.right.val == x:
                    parent_x = node
                if node.right.val == y:
                    parent_y = node
                q.append(node.right)

            if parent_x and parent_y and parent_x != parent_y:
                return True

        return False
