Cousins in Binary Tree - Video Solutions
Cousins in a binary tree | Leetcode #993
Cousins in Binary Tree - Video Solution
Watch 10 video solutions for Cousins in Binary Tree, a easy level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by Techdose has 39,870 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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. |