993. Cousins in Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree,Breadth-first Search
FAANG asked: 1
Acceptance rate: 52.3%
Problem Breakdown
The problem asks us to determine if two nodes in a binary tree are cousins. Two nodes are considered cousins if they are at the same depth but have different parents. We are given the root of the binary tree and the values of the two nodes we need to check.
Inputs:
root: The root node of the binary tree.x: The value of one node.y: The value of another node.
Outputs:
- A boolean value indicating whether the nodes with values
xandyare cousins.
Implicit Constraints or Tricky Edge Cases:
- The tree can have between 2 and 100 nodes.
- Each node has a unique integer value from 1 to 100.
- The root node is at depth 0.
- If either
xoryis the root, they cannot be cousins since they would not have parents.
Intuition
A brute-force approach would involve traversing the tree to find the depths and parents of both nodes. However, this could lead to a high time complexity as we might need to traverse parts of the tree multiple times. A better approach is to use a breadth-first search (BFS) to level-order traverse the tree while keeping track of the parent of each node. This way, we can efficiently determine if x and y are at the same depth but have different parents.
Approach
We will use a BFS traversal to explore the tree level by level. For each node, we will keep track of its value, its parent, and its depth. We will use a queue to facilitate the BFS traversal. As we traverse the tree, we will check if we encounter either x or y. If we do, we will store their respective depths and parents. After traversing the entire level, we will compare the depths and parents of x and y. If they have the same depth but different parents, they are cousins.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. We need to visit each node once.
- Space Complexity: O(n) in the worst case due to the queue used for BFS and the space required to store the depths and parents of
xandy.
Solution
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 areCousins(root: TreeNode, x: int, y: int) -> bool:
if root is None or (root.val == x or root.val == y):
return False
queue = deque([(root, 0, None)]) # (node, depth, parent)
x_depth, x_parent = None, None
y_depth, y_parent = None, None
while queue:
level_size = len(queue)
for _ in range(level_size):
node, depth, parent = queue.popleft()
if node.val == x:
x_depth, x_parent = depth, parent
elif node.val == y:
y_depth, y_parent = depth, parent
if x_depth is not None and y_depth is not None:
break
if node.left:
queue.append((node.left, depth + 1, node))
if node.right:
queue.append((node.right, depth + 1, node))
if x_depth is not None and y_depth is not None:
break
return x_depth == y_depth and x_parent != y_parent
Edge Cases Handled
- Root Node: If either
xoryis the root, they cannot be cousins since they do not have parents. - Single Level Tree: If the tree has only one level (i.e., no children),
xandycannot be cousins unless they are both the root. - Identical Values: The problem guarantees that all node values are unique, so we don’t need to handle duplicate values.