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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cousins in Binary Tree

Difficulty: Easy

Problem Description

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.

Key Insights

  • Two nodes are cousins if they are at the same depth in the tree.
  • The nodes must have different parents to qualify as cousins.
  • A depth-first search (DFS) or breadth-first search (BFS) can be used to traverse the tree and find the required nodes.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, as we may visit each node once. Space Complexity: O(H) - where H is the height of the tree, which is the space complexity of the call stack in the case of DFS or the queue in the case of BFS.

Solution

To determine if two nodes are cousins, we can use a breadth-first search (BFS) approach. We will traverse the binary tree level by level, keeping track of the depth of each node and their parent. When we find both nodes x and y, we can check if they have the same depth and different parents.

  1. Use a queue to keep track of nodes to explore and their respective parent and depth.
  2. For each node, we check its children and enqueue them with updated depth and parent information.
  3. If we find both nodes, we compare their depths and parents to determine if they are cousins.

Code Solutions

from collections import deque

def isCousins(root, x, y):
    queue = deque([(root, None, 0)])  # (node, parent, depth)
    x_parent = y_parent = None
    x_depth = y_depth = -1

    while queue:
        node, parent, depth = queue.popleft()

        if node.val == x:
            x_parent, x_depth = parent, depth
        if node.val == y:
            y_parent, y_depth = parent, depth
        
        if x_parent is not None and y_parent is not None:
            break

        if node.left:
            queue.append((node.left, node, depth + 1))
        if node.right:
            queue.append((node.right, node, depth + 1))

    return x_depth == y_depth and x_parent != y_parent
← Back to All Questions