Domain 1EasyCORE

Cousins in Binary Tree

The problem asks us to determine if two nodes in a binary tree are cousins. Two nodes are considered cousins if they are at the same depth but have different parents. We are given the root of the binary tree and the values of the two nodes we need to check.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Breadth-first Search

993. Cousins in Binary Tree

Model: qwen2.5-coder:14b
Topics: Tree,Breadth-first Search
FAANG asked: 1
Acceptance rate: 52.3%


Problem Breakdown

The problem asks us to determine if two nodes in a binary tree are cousins. Two nodes are considered cousins if they are at the same depth but have different parents. We are given the root of the binary tree and the values of the two nodes we need to check.

Inputs:

  • root: The root node of the binary tree.
  • x: The value of one node.
  • y: The value of another node.

Outputs:

  • A boolean value indicating whether the nodes with values x and y are cousins.

Implicit Constraints or Tricky Edge Cases:

  • The tree can have between 2 and 100 nodes.
  • Each node has a unique integer value from 1 to 100.
  • The root node is at depth 0.
  • If either x or y is the root, they cannot be cousins since they would not have parents.

Intuition

A brute-force approach would involve traversing the tree to find the depths and parents of both nodes. However, this could lead to a high time complexity as we might need to traverse parts of the tree multiple times. A better approach is to use a breadth-first search (BFS) to level-order traverse the tree while keeping track of the parent of each node. This way, we can efficiently determine if x and y are at the same depth but have different parents.

Approach

We will use a BFS traversal to explore the tree level by level. For each node, we will keep track of its value, its parent, and its depth. We will use a queue to facilitate the BFS traversal. As we traverse the tree, we will check if we encounter either x or y. If we do, we will store their respective depths and parents. After traversing the entire level, we will compare the depths and parents of x and y. If they have the same depth but different parents, they are cousins.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. We need to visit each node once.
  • Space Complexity: O(n) in the worst case due to the queue used for BFS and the space required to store the depths and parents of x and y.

Solution

from collections import deque

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

def areCousins(root: TreeNode, x: int, y: int) -> bool:
    if root is None or (root.val == x or root.val == y):
        return False
    
    queue = deque([(root, 0, None)])  # (node, depth, parent)
    x_depth, x_parent = None, None
    y_depth, y_parent = None, None
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            node, depth, parent = queue.popleft()
            
            if node.val == x:
                x_depth, x_parent = depth, parent
            elif node.val == y:
                y_depth, y_parent = depth, parent
            
            if x_depth is not None and y_depth is not None:
                break
            
            if node.left:
                queue.append((node.left, depth + 1, node))
            if node.right:
                queue.append((node.right, depth + 1, node))
        
        if x_depth is not None and y_depth is not None:
            break
    
    return x_depth == y_depth and x_parent != y_parent

Edge Cases Handled

  • Root Node: If either x or y is the root, they cannot be cousins since they do not have parents.
  • Single Level Tree: If the tree has only one level (i.e., no children), x and y cannot be cousins unless they are both the root.
  • Identical Values: The problem guarantees that all node values are unique, so we don’t need to handle duplicate values.