Cousins in Binary Tree - Solution & Explanation
Problem Statement
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:
- The number of nodes in the tree is in the range
[2, 100]. 1 <= Node.val <= 100- Each node has a unique value.
x != yxandyare exist in the tree.
Approach Overview
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.
Approach 1: Level Order Traversal
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.
Code
Python
JavaScript
C++
Complexity
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.
Approach 2: Depth First Search with Parent and Depth Tracking
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.
Code
Python
JavaScript
C++
Complexity
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.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Cousins in a binary tree | Leetcode #993 • Techdose • 39,870 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Cousins in Binary Tree easy or hard?
Cousins in Binary Tree Python/Java solution
How to solve Cousins in Binary Tree in O(n)?
What is the best approach for Cousins in Binary Tree?
Is Cousins in Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Cousins in Binary Tree?
What is the time complexity of Cousins in Binary Tree?
Ready to solve this problem?
Practice Cousins in Binary Tree with our built-in code editor and test cases.
Practice on FleetCode