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:
[2, 100].1 <= Node.val <= 100x != yx and y are exist in the tree.Problem Overview: Given a binary tree and two node values x and y, determine if the nodes are cousins. Two nodes are cousins if they are at the same depth but have different parents.
Approach 1: Level Order Traversal (O(n) time, O(n) space)
This approach uses Breadth-First Search to traverse the tree level by level. Process nodes using a queue and examine each level independently. While scanning a level, track whether x and y appear and ensure they do not share the same parent. If both values appear in the same level and have different parents, they are cousins. If only one appears in the level, they cannot be cousins. This approach works naturally because BFS groups nodes by depth, which directly matches the cousin definition.
Approach 2: Depth First Search with Parent and Depth Tracking (O(n) time, O(h) space)
This method performs a Depth-First Search on the binary tree while tracking two values for every node: its parent and its depth. During traversal, record the parent node and depth when x or y is found. After the traversal completes, compare the results. The nodes are cousins if their depths are equal but their parent references differ. DFS is slightly more space-efficient when the tree height h is small because the recursion stack grows with the height rather than the total number of nodes.
Recommended for interviews: Level Order Traversal is usually the first solution interviewers expect because the cousin definition directly maps to levels in BFS. Checking siblings during each level also avoids storing extra metadata. The DFS parent-depth method demonstrates deeper understanding of tree traversal and state tracking. Both run in O(n) time, but BFS is often easier to reason about under interview pressure.
This approach utilizes Level Order Traversal (Breadth-First) to determine if two nodes are cousins. During traversal, track the parent and depth of each node until both target nodes are found, then verify if they qualify as cousins.
In this Python solution, we use a deque to facilitate a level-order traversal. We track both the parent and depth of each node and check if the target nodes are at the same depth but have different parents. If they do, they are cousins.
Python
JavaScript
C++
Time Complexity: O(n), where n is the number of nodes in the tree, as it requires visiting each node once.
Space Complexity: O(n) for storing the nodes in the queue.
This approach uses a DFS to recursively track the parent and depth of each node. On finding nodes x and y, checks are done whether they meet cousin criteria (same depth and different parents).
This Python implementation uses DFS to recursively find the depth and parents of x and y. When both found, checks are done to validate if they are cousins by comparing depth and parent values.
Python
JavaScript
C++
Time Complexity: O(n) where n is the total nodes count due to entire tree traversal.
Space Complexity: O(h) with h as the height of the tree, due to recursive stack space usage.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Level Order Traversal | Time Complexity: O(n), where n is the number of nodes in the tree, as it requires visiting each node once. |
| Depth First Search with Parent and Depth Tracking | Time Complexity: O(n) where n is the total nodes count due to entire tree traversal. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal (BFS) | O(n) | O(n) | Best when reasoning about tree levels directly and checking sibling relationships within the same level. |
| DFS with Parent and Depth Tracking | O(n) | O(h) | Useful when you prefer recursive traversal or want to track node metadata like parent and depth. |
Cousins in a binary tree | Leetcode #993 • Techdose • 39,470 views views
Watch 9 more video solutions →Practice Cousins in Binary Tree with our built-in code editor and test cases.
Practice on FleetCode