algoadvance

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.

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

Clarifying Questions

  1. Tree Properties: Can I assume that the tree does not contain any cycles and all values are unique?
  2. Input Constraints: What are the constraints on the size of the tree and the values of x and y?

Assumed answers:

  1. Yes, the tree does not contain cycles and all node values are unique.
  2. The tree can have up to 10^4 nodes and the values x and y are unique integers that are guaranteed to be in the tree.

Strategy

To determine if two nodes are cousins, we need to ensure:

  1. They are at the same depth.
  2. They have different parents.

We can accomplish this using a Breadth-First Search (BFS) approach:

  1. Traverse the tree level-by-level.
  2. For each node, we keep track of its parent and its depth.
  3. Once we find both nodes x and y, we compare their depths and parents.

Code

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 isCousins(root, x, y):
    if not root:
        return False

    queue = deque([(root, None, 0)])  # node, parent, depth
    x_info = y_info = None

    while queue:
        node, parent, depth = queue.popleft()
        
        if node.val == x:
            x_info = (parent, depth)
        if node.val == y:
            y_info = (parent, depth)
        
        if x_info and y_info:
            break
        
        if node.left:
            queue.append((node.left, node, depth + 1))
        if node.right:
            queue.append((node.right, node, depth + 1))
    
    if x_info and y_info:
        return x_info[1] == y_info[1] and x_info[0] != y_info[0]
    return False

Explanation

  1. Initialization: We initialize a queue to perform BFS, starting with the root node. Each element in the queue contains the node, its parent, and its depth.
  2. BFS Traversal: We process nodes in level-order. For each node, if it’s either x or y, we note its parent and depth.
  3. Check Conditions: Once both x and y are found, we compare their depths and parents to determine if they are cousins.
  4. Return Result: If both nodes are found and meet the cousin criteria, we return True. Otherwise, we return False.

Time Complexity

This approach ensures that we efficiently determine whether two nodes are cousins by leveraging BFS to capture their depth and parent information.

Try our interview co-pilot at AlgoAdvance.com