Cousins in Binary Tree

Problem Statement

In this task, we are given the root of a binary tree where each node has unique values, along with two specific values x and y representing different nodes in the tree. We must determine if the nodes corresponding to these values are "cousins". For clarification, cousins in a binary tree are defined as nodes that are at the same depth (or level) but do not share the same parent. The task involves checking the relationship between the nodes corresponding to x and y according to these definitions and returning true if they are cousins, otherwise returning false.

Examples

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 is in the range [2, 100].
• 1 <= Node.val <= 100
• Each node has a unique value.
• x != y
• x and y are exist in the tree.

Approach and Intuition

• To solve the problem, we need to determine if the nodes x and y are at the same depth yet have different parents. This leads us to using a breadth-first search (BFS), which provides a systematic method for exploring the tree level by level.

  1. Initiate a queue that will include nodes alongside their corresponding depth and their parent information. Start with the root node having depth 0 and no parent (null).

  2. Process the nodes in the queue:

     • For each node, check its children.
     • If a child is either x or y, store its depth and its parent.
     • Put the child into the queue with incremented depth and current node as the parent.

  3. After populating the parent and depth information for both x and y (or determining that one/both are absent in the tree), compare their depths and parents:

     • Cousins are identified by having the same depth but different parents.

• Given the constraints:

  • Since each node value must be unique, there's no ambiguity in node identification.
  • The tree size range ([2, 100]) ensures our BFS approach remains efficient.
  • Verification includes checking if both x and y actually exist in the tree as given by the constraint x and y are exist in the tree.

• Using the examples provided:

  • The first example, with nodes [1,2,3,4] and x = 4, y = 3, shows x and y at different depths, resulting in false.
  • In the second example, in the tree [1,2,3,null,4,null,5], x = 5 and y = 4 are at the same depth and do not share the same parent, thus true.
  • The third example shows a sibling relationship (x = 2 and y = 3 share the same parent), which mean they are not cousins, hence false.

Through following this approach and set of checks, one can effectively and accurately determine cousin relationships in a binary tree as defined.

Solutions

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;
    }
}