Introduction

In this blog post, we will explore how to solve the LeetCode problem "993" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise. Two nodes of a binary tree are cousins if they have the same depth with different parents. Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1. 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.

Explanation

Here's the breakdown of the approach and the Python code:

• High-level approach:

  • Use Breadth-First Search (BFS) to traverse the tree level by level.
  • For each level, check if x and y are present. If both are present, verify they have different parents.
  • If only one of x or y is found at a particular level, then they can't be cousins, so return False.

• Complexity:

  • Runtime: O(N), where N is the number of nodes in the tree.
  • Storage: O(W), where W is the maximum width of the tree (for the queue in BFS). In the worst case (a complete binary tree), W can be O(N).

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: TreeNode, x: int, y: int) -> bool:
    """
    Determines if two nodes in a binary tree are cousins.

    Args:
        root: The root of the binary tree.
        x: The value of the first node.
        y: The value of the second node.

    Returns:
        True if the nodes with values x and y are cousins, False otherwise.
    """

    if not root:
        return False

    queue = deque([root])

    while queue:
        level_size = len(queue)
        x_found = False
        y_found = False
        x_parent = None
        y_parent = None

        for _ in range(level_size):
            node = queue.popleft()

            if node.left:
                if node.left.val == x:
                    x_found = True
                    x_parent = node
                elif node.left.val == y:
                    y_found = True
                    y_parent = node
                queue.append(node.left)

            if node.right:
                if node.right.val == x:
                    x_found = True
                    x_parent = node
                elif node.right.val == y:
                    y_found = True
                    y_parent = node
                queue.append(node.right)

        if x_found and y_found:
            return x_parent != y_parent
        elif x_found or y_found:
            return False

    return False