We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cousins in Binary Tree

Number: 1035

Difficulty: Easy

Paid? No

Companies: Amazon, Meta, Google, Microsoft, TikTok, Adobe, Bloomberg

Problem Description

A binary tree with unique values is provided along with two distinct values, x and y. You must determine whether the nodes corresponding to x and y are cousins, meaning they are on the same level (depth) in the tree but have different parents.

Key Insights

  • Cousins are defined by being at the same depth in the tree but having different parent nodes.
  • Breadth-first search (BFS) is a natural choice as it processes nodes level by level.
  • During a level traversal, record the parent of each target node (x and y).
  • If both nodes are discovered in the same level and have different parents, then they are cousins.
  • If only one node is found in a level, or if both are found but share the same parent, they are not cousins.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since every node may be visited once. Space Complexity: O(n), for storing nodes in the queue during BFS (or recursion stack in DFS in the worst case).

Solution

We use a BFS approach to traverse the tree level-by-level. For each level:

  1. Process all nodes and record the parent for x and y if found.
  2. If both x and y are found in the same level, check if their parents are different. If so, return true.
  3. If only one is found in the current level, the nodes do not reside at the same depth, so return false. This level-by-level checking ensures that the depth condition is met while verifying the parent condition.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java.

# Python solution using BFS
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isCousins(root: TreeNode, x: int, y: int) -> bool:
    if not root:
        return False
    
    # Queue for BFS: each element is a tuple (node, parent)
    queue = deque([(root, None)])
    
    while queue:
        level_size = len(queue)
        x_parent, y_parent = None, None
        
        # Process nodes of the current level
        for _ in range(level_size):
            node, parent = queue.popleft()
            if node.val == x:
                x_parent = parent
            if node.val == y:
                y_parent = parent
            if node.left:
                queue.append((node.left, node))
            if node.right:
                queue.append((node.right, node))
        
        # If both nodes are found on the same level, check if they have different parents
        if x_parent and y_parent:
            return x_parent != y_parent
        # If only one target node is found at this level, they are not cousins.
        if (x_parent and not y_parent) or (y_parent and not x_parent):
            return False

    return False
← Back to All Questions