Cousins in Binary Tree

class Solution {

    public boolean checkCousins(TreeNode root, int x, int y) {
        // Use queue for level order traversal
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while (!q.isEmpty()) {
            boolean isSibling = false;
            boolean isCousin = false;

            int levelSize = q.size();

            for (int i = 0; i < levelSize; ++i) {
                TreeNode current = q.poll();

                if (current == null) isSibling = false; // Reset sibling status at each boundary.
                else {
                    if (current.val == x || current.val == y) {
                        if (!isCousin) {
                            isSibling = isCousin = true;
                        } else {
                            return !isSibling;
                        }
                    }

                    if (current.left != null) q.add(current.left);
                    if (current.right != null) q.add(current.right);
                    q.add(null); // Define a boundary for siblings.
                }
            }
            if (isCousin) return false; // Found only one node of interest.
        }
        return false;
    }
}

This Java solution checks whether two nodes in a binary tree are cousins. Cousins are nodes that are on the same level but have different parents. The method checkCousins utilizes level order traversal (using breadth-first search) to explore the tree and compare nodes.

• Start by initializing a queue and adding the root node to it.
• Continue with a loop that processes nodes until the queue is empty.
• At each level of the tree:
  • Initialize flags, isSibling and isCousin, to manage sibling status and cousin detection.
  • Determine the number of nodes at the current level with levelSize, indicating how many nodes to process for this iteration.
  • Loop through each node at the current level:
    • Poll the node from the queue to process it.
    • If the node is null, reset the isSibling flag. A null node acts as a marker to differentiate potential sibling groups.
    • Identify if the current node’s value matches either of the values being checked (x or y):
      • If one match is found and isCousin is false, set isSibling and isCousin to true.
      • If a second match is found and isSibling is true, return !isSibling to confirm they are cousins (since they shouldn’t be siblings).
    • Push the left and right children of the current node into the queue.
    • Push null into the queue after adding children to maintain sibling boundaries.
  • If only one of the nodes (either x or y) is found (isCousin is true) and there was no sibling matched (isSibling is false), continue to the next level.
• Finally, if no companionship have been determined by the end of the loop, return false as the nodes are neither at the same level nor disconnected from having the same parent.

This method ensures that you efficiently identify if two nodes are cousins by maintaining clear control of level boundaries and sibling relationships.

from collections import deque

class Solution:

    def checkCousins(self, root: TreeNode, p: int, q: int) -> bool:

        # Initialize BFS queue
        bfs_queue = deque([root])

        while bfs_queue:

            at_same_level = False
            found_cousins = False
            level_size = len(bfs_queue)
            for _ in range(level_size):

                # Dequeue element
                curr_node = bfs_queue.popleft()  

                # Check if it's None that marks different parent boundary
                if curr_node is None:
                    at_same_level = False
                else:
                    # Check if current is either p or q
                    if curr_node.val == p or curr_node.val == q:
                        # If first of p or q is found at this level
                        if not found_cousins:
                            at_same_level, found_cousins = True, True
                        else:
                            # if they are still within the same parent boundary
                            return not at_same_level

                    # Continue BFS with children
                    if curr_node.left:
                        bfs_queue.append(curr_node.left)
                    if curr_node.right:
                        bfs_queue.append(curr_node.right)
                    # Marker for different parents
                    bfs_queue.append(None)
                    
            # Only one of p or q found at this level
            if found_cousins:
                return False

        return False

In the provided Python code, you can determine if two nodes in a binary tree are cousins. The code employs a Breadth-First Search (BFS) strategy using a queue to traverse the tree level by level.

• Begin by initializing a deque to facilitate the BFS, starting with the root node.
• Use a while loop to process nodes until the queue is empty. For each level of the BFS:
  • Initialize flags at_same_level to monitor if a found node's sibling might be the cousin and found_cousins to check if one of the cousin candidates was found at the current level.
  • Determine level_size as the count of nodes at the current tree level.
  • Iterate over each node of the current level:
    • Dequeue the front node.
    • Check if it is None which indicates the boundary between different parents within the same level.
    • Validate if the current node matches one of the target values (p or q). If a match is found:
      • Set found_cousins to True. If another target is found later in the same breadth level but before the next None, they are cousins from different parents.
      • Check at_same_level to return a negative result if another target value is found after another sibling - indicating they are siblings instead of cousins.
    • If the current node has children, enqueue them and place None as a marker for potential different parent boundaries.
  • If after scanning a level only one target is found, determine that the other must be at a different level, thus not making them cousins, and return False.
• Execute BFS until all levels are visited. If no conclusive results emerge during the traversal, return False.

This Python code ensures an efficient check on whether two nodes are cousins in a binary tree without revisiting nodes or retaining unnecessary data, making use of the characteristics of BFS and control flags to ascertain cousin relation based on tree levels and parent boundaries.