How do you solve Cousins in Binary Tree on LeetCode?

Cousins in Binary Tree (LeetCode #993) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Cousins must be on the same level but have different parents.

What is the brute force solution for Cousins in Binary Tree?

The brute force approach for Cousins in Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each node to find both x and y, then verifies their depth and parents. It’s straightforward but inefficient as it may involve multiple traversals of the tree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Cousins in Binary Tree?

Cousins in Binary Tree uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Breadth-First Search (BFS), Depth-First Search (DFS).

What are the interview tips for Cousins in Binary Tree?

Always clarify the definition of cousins before jumping into the solution. Consider edge cases, such as when one node is a direct child of the other. Explain your thought process clearly as you write your code.

What are common mistakes when solving Cousins in Binary Tree?

Not checking if both nodes are found before comparing their parents. Assuming that nodes are always at the same depth without verifying.

#993

Cousins in Binary Tree

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeBreadth-First Search (BFS)Depth-First Search (DFS)

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a single traversal of the tree to gather the necessary information about both nodes, making it efficient. We can use a queue for a breadth-first search (BFS) to find both nodes in one go.

⚙️

Algorithm

3 steps

1Step 1: Perform a breadth-first search (BFS) to traverse the tree level by level.
2Step 2: For each level, check if both nodes x and y are present. If found, check their parents.
3Step 3: If both nodes are found on the same level with different parents, return true; otherwise, return false.

solution.py33 lines

1# Full working Python code
2from collections import deque
3
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
12        queue = deque([(root, None)])
13        while queue:
14            size = len(queue)
15            found_x = found_y = False
16            parent_x = parent_y = None
17            for _ in range(size):
18                node, parent = queue.popleft()
19                if node.val == x:
20                    found_x = True
21                    parent_x = parent
22                if node.val == y:
23                    found_y = True
24                    parent_y = parent
25                if node.left:
26                    queue.append((node.left, node))
27                if node.right:
28                    queue.append((node.right, node))
29            if found_x and found_y:
30                return parent_x != parent_y
31            if found_x or found_y:
32                return False
33        return False

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(n) due to the queue used for BFS, which can hold all nodes at the maximum level.

1Cousins must be on the same level but have different parents.
2A single traversal can gather all necessary information about both nodes.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.