# LeetCode 993: Cousins in Binary Tree ## Problem Restatement We are given the root of a binary tree with unique values. We are also given two different values: ```python x y ``` Both values exist in the tree. We need to return `True` if the nodes with values `x` and `y` are cousins. Two nodes are cousins if: | Condition | Meaning | |---|---| | Same depth | They are on the same tree level | | Different parents | They do not share the same immediate parent | The root has depth `0`. Children of a node at depth `d` have depth `d + 1`. ## Input and Output | Item | Meaning | |---|---| | Input | Root of a binary tree, and two node values `x` and `y` | | Output | Boolean | | Cousin condition | Same depth, different parents | | Important detail | Values are unique, and both `x` and `y` exist | Function shape: ```python def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool: ... ``` ## Examples Example 1: ```python root = [1, 2, 3, 4] x = 4 y = 3 ``` Tree: ```text 1 / \ 2 3 / 4 ``` Node `4` has depth `2`. Node `3` has depth `1`. They are not at the same depth. Answer: ```python False ``` Example 2: ```python root = [1, 2, 3, None, 4, None, 5] x = 5 y = 4 ``` Tree: ```text 1 / \ 2 3 \ \ 4 5 ``` Node `4` and node `5` are both at depth `2`. Their parents are different: `2` and `3`. Answer: ```python True ``` Example 3: ```python root = [1, 2, 3, None, 4] x = 2 y = 3 ``` Node `2` and node `3` are at the same depth, but they have the same parent: node `1`. They are siblings, not cousins. Answer: ```python False ``` ## First Thought: Find Depth and Parent To decide whether two nodes are cousins, we need two pieces of information for each target node: | Value | Needed information | |---|---| | `x` | Its depth and parent | | `y` | Its depth and parent | After finding both nodes: ```python same_depth = depth_x == depth_y different_parent = parent_x != parent_y ``` The answer is: ```python same_depth and different_parent ``` We can collect this information with either DFS or BFS. ## Key Insight BFS is natural because it processes the tree level by level. At each level: 1. Check whether `x` appears. 2. Check whether `y` appears. 3. Record their parents. 4. After finishing the level, decide whether they are cousins. If both are found in the same level, they have the same depth. Then they are cousins only if their parents are different. If only one is found in a level, the other one must be at a different depth, so they cannot be cousins. ## Algorithm Use a queue containing pairs: ```python (node, parent) ``` Start with: ```python (root, None) ``` While the queue is not empty: 1. Process exactly one level. 2. Set `parent_x = None` and `parent_y = None`. 3. For each node in the current level: - If `node.val == x`, store its parent. - If `node.val == y`, store its parent. - Push children into the queue with the current node as parent. 4. After the level: - If both parents were found, return whether they are different. - If exactly one was found, return `False`. If the loop ends, return `False`. ## Correctness BFS processes all nodes at depth `d` before any node at depth `d + 1`. During each level, the algorithm records the parent of `x` if `x` appears at that depth, and the parent of `y` if `y` appears at that depth. If both are found during the same level, then they have the same depth. They are cousins exactly when their recorded parents are different, so returning that comparison is correct. If only one target is found during a level, then the other target cannot be at that same depth. Since BFS will only move deeper afterward, the two nodes have different depths. They cannot be cousins, so returning `False` is correct. Because both target values exist and BFS eventually visits every node, the algorithm correctly determines whether the two target nodes are cousins. ## Complexity Let `n` be the number of nodes and `w` be the maximum width of the tree. | Metric | Value | Why | |---|---:|---| | Time | `O(n)` | Each node is processed at most once | | Space | `O(w)` | The queue stores one level of nodes | In the worst case, `w` can be `O(n)`. ## Implementation ```python from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool: queue = deque([(root, None)]) while queue: level_size = len(queue) parent_x = None parent_y = None for _ in range(level_size): node, parent = queue.popleft() if node.val == x: parent_x = parent if node.val == y: parent_y = parent if node.left: queue.append((node.left, node)) if node.right: queue.append((node.right, node)) if parent_x is not None and parent_y is not None: return parent_x != parent_y if parent_x is not None or parent_y is not None: return False return False ``` ## Code Explanation The queue stores each node together with its parent: ```python queue = deque([(root, None)]) ``` For each loop iteration, we process one full depth level: ```python level_size = len(queue) ``` At the start of each level, we have not found either target: ```python parent_x = None parent_y = None ``` When a target appears, store its parent: ```python if node.val == x: parent_x = parent if node.val == y: parent_y = parent ``` Children are pushed with the current node as their parent: ```python if node.left: queue.append((node.left, node)) if node.right: queue.append((node.right, node)) ``` After finishing the level, if both targets were found, they have the same depth: ```python if parent_x is not None and parent_y is not None: return parent_x != parent_y ``` If only one target was found, they are at different depths: ```python if parent_x is not None or parent_y is not None: return False ``` ## Testing ```python from collections import deque from typing import Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def run_tests(): s = Solution() root1 = TreeNode( 1, TreeNode(2, TreeNode(4)), TreeNode(3), ) assert s.isCousins(root1, 4, 3) is False root2 = TreeNode( 1, TreeNode(2, None, TreeNode(4)), TreeNode(3, None, TreeNode(5)), ) assert s.isCousins(root2, 5, 4) is True root3 = TreeNode( 1, TreeNode(2, None, TreeNode(4)), TreeNode(3), ) assert s.isCousins(root3, 2, 3) is False root4 = TreeNode( 1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3), ) assert s.isCousins(root4, 4, 5) is False print("all tests passed") run_tests() ``` | Test | Expected | Why | |---|---:|---| | `x = 4`, `y = 3` | `False` | Different depths | | `x = 5`, `y = 4` | `True` | Same depth, different parents | | `x = 2`, `y = 3` | `False` | Same parent | | `x = 4`, `y = 5` | `False` | Siblings, not cousins |