Cousins in Binary Tree solution and explanation
Google
9 more videos on this problem
Cousins in a binary tree | Leetcode #993Techdose · 12:12 · 39K views
Cousins In Binary Tree LeetCode Java | LeetCode 993 | Programming TutorialsProgramming Tutorials · 12:36 · 2K views
Cousins in Binary Tree | cousins in binary tree | cousins in binary tree leetcode | leetcode 993Akshay Goyal · 6:41 · 2K views
Leetcode 993 Cousins in Binary TreeRen Zhang · 6:40 · 1K views
Daily Leetcode #566: Oct 18, 2021 - 993. Cousins in Binary TreeProgramming Live with Larry · 5:34 · 343 views
Cousins in Binary Tree | LeetCode 993 | Coders CampCoders Camp · 8:53 · 271 views
Cousins in Binary Tree | Leetcode 993 | Amazon Google Facebook interview questionSuper Lazy Coder · 12:20 · 257 views
Cousins in Binary Tree (Leetcode 993) | LeetCode TutorialJomaClass · 10:59 · 225 views
993 Cousins in Binary Tree LeetCode CPP SolutionAnimated Anand · 9:34 · 192 views
LeetCode 993 - Cousins in Binary Tree: A Microsoft JourneyThe Lofi Dev · 7:19 · 174 views
The problem
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.
from collections import deque
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: TreeNode, x: int, y: int) -> bool:
queue = deque([(root, None)]) # (node, parent)
x_info = y_info = None
while queue:
level_length = len(queue)
for i in range(level_length):
node, parent = queue.popleft()
if node.val == x:
x_info = (node, parent)
elif node.val == y:
y_info = (node, parent)
if x_info and y_info:
break
if node.left:
queue.append((node.left, node))
if node.right:
queue.append((node.right, node))
if x_info and y_info:
# Check if they are cousins (same depth but different parents)
return x_info[1] != y_info[1]
if x_info or y_info:
# Found one node but not the other in the same level
return False
return False#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
queue<pair<TreeNode*, TreeNode*>> q; // node, parent
q.push({root, nullptr});
pair<TreeNode*, TreeNode*> xInfo = {nullptr, nullptr}, yInfo = {nullptr, nullptr};
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
auto [node, parent] = q.front();
q.pop();
if (node->val == x) xInfo = {node, parent};
if (node->val == y) yInfo = {node, parent};
if (xInfo.first && yInfo.first) break;
if (node->left) q.push({node->left, node});
if (node->right) q.push({node->right, node});
}
if (xInfo.first && yInfo.first)
return xInfo.second != yInfo.second;
if (xInfo.first || yInfo.first)
return false;
}
return false;
}
};function TreeNode(val, left, right) {
this.val = val;
this.left = left || null;
this.right = right || null;
}
var isCousins = function(root, x, y) {
const queue = [{ node: root, parent: null }];
let xInfo = null, yInfo = null;
while (queue.length) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const { node, parent } = queue.shift();
if (node.val === x) xInfo = { node, parent };
if (node.val === y) yInfo = { node, parent };
if (xInfo && yInfo) break;
if (node.left) queue.push({ node: node.left, parent: node });
if (node.right) queue.push({ node: node.right, parent: node });
}
if (xInfo && yInfo) return xInfo.parent !== yInfo.parent;
if (xInfo || yInfo) return false;
}
return false;
};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.
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).
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: TreeNode, x: int, y: int) -> bool:
def dfs(node, parent, depth, node_info):
if not node:
return
if node.val == x:
node_info.append((depth, parent))
if node.val == y:
node_info.append((depth, parent))
dfs(node.left, node, depth + 1, node_info)
dfs(node.right, node, depth + 1, node_info)
node_info = []
dfs(root, None, 0, node_info)
x_depth, x_parent = node_info[0]
y_depth, y_parent = node_info[1]
return x_depth == y_depth and x_parent != y_parent#include <utility>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
pair<int, TreeNode*> xInfo = {0, nullptr}, yInfo = {0, nullptr};
dfs(root, nullptr, 0, x, y, xInfo, yInfo);
return xInfo.first == yInfo.first && xInfo.second != yInfo.second;
}
private:
void dfs(TreeNode* node, TreeNode* parent, int depth, int x, int y,
pair<int, TreeNode*>& xInfo, pair<int, TreeNode*>& yInfo) {
if (!node) return;
if (node->val == x) xInfo = {depth, parent};
if (node->val == y) yInfo = {depth, parent};
dfs(node->left, node, depth + 1, x, y, xInfo, yInfo);
dfs(node->right, node, depth + 1, x, y, xInfo, yInfo);
}
};function TreeNode(val, left, right) {
this.val = val;
this.left = left || null;
this.right = right || null;
}
var isCousins = function(root, x, y) {
const nodeInfo = [];
function dfs(node, parent, depth) {
if (!node) return;
if (node.val === x || node.val === y) {
nodeInfo.push({depth, parent});
}
dfs(node.left, node, depth + 1);
dfs(node.right, node, depth + 1);
}
dfs(root, null, 0);
return nodeInfo[0].depth === nodeInfo[1].depth && nodeInfo[0].parent !== nodeInfo[1].parent;
};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.
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
Deque<TreeNode[]> q = new ArrayDeque<>();
q.offer(new TreeNode[] {root, null});
int d1 = 0, d2 = 0;
TreeNode p1 = null, p2 = null;
for (int depth = 0; !q.isEmpty(); ++depth) {
for (int n = q.size(); n > 0; --n) {
TreeNode[] t = q.poll();
TreeNode node = t[0], parent = t[1];
if (node.val == x) {
d1 = depth;
p1 = parent;
} else if (node.val == y) {
d2 = depth;
p2 = parent;
}
if (node.left != null) {
q.offer(new TreeNode[] {node.left, node});
}
if (node.right != null) {
q.offer(new TreeNode[] {node.right, node});
}
}
}
return p1 != p2 && d1 == d2;
}
}/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
let [d1, d2] = [0, 0];
let [p1, p2] = [null, null];
const q: [TreeNode, TreeNode][] = [[root, null]];
for (let depth = 0; q.length > 0; ++depth) {
const t: [TreeNode, TreeNode][] = [];
for (const [node, parent] of q) {
if (node.val === x) {
[d1, p1] = [depth, parent];
} else if (node.val === y) {
[d2, p2] = [depth, parent];
}
if (node.left) {
t.push([node.left, node]);
}
if (node.right) {
t.push([node.right, node]);
}
}
q.splice(0, q.length, ...t);
}
return d1 === d2 && p1 !== p2;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isCousins(root *TreeNode, x int, y int) bool {
type pair struct{ node, parent *TreeNode }
var d1, d2 int
var p1, p2 *TreeNode
q := []pair{{root, nil}}
for depth := 0; len(q) > 0; depth++ {
for n := len(q); n > 0; n-- {
node, parent := q[0].node, q[0].parent
q = q[1:]
if node.Val == x {
d1, p1 = depth, parent
} else if node.Val == y {
d2, p2 = depth, parent
}
if node.Left != nil {
q = append(q, pair{node.Left, node})
}
if node.Right != nil {
q = append(q, pair{node.Right, node})
}
}
}
return d1 == d2 && p1 != p2
}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 | – |
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. |
Frequently asked questions
Is Cousins in Binary Tree easy or hard?
Cousins in Binary Tree is classified as an Easy problem on LeetCode. It mainly tests basic binary tree traversal concepts such as BFS levels and DFS depth tracking rather than advanced algorithms.
Cousins in Binary Tree Python/Java solution
The problem can be implemented in Python, Java, or C++ using either BFS or DFS. Python commonly uses a deque for BFS or recursion for DFS. Java and C++ typically use a queue for level order traversal or recursive helper functions to track parent and depth.
How to solve Cousins in Binary Tree in O(n)?
Traverse the tree once and track depth and parent information for the two target nodes. With BFS, scan each level and check if both nodes appear without sharing the same parent. With DFS, record the parent and depth when each node is found, then verify equal depth and different parents.
What is the best approach for Cousins in Binary Tree?
Level Order Traversal using Breadth-First Search is the most intuitive approach. BFS processes the tree level by level, making it easy to check whether two nodes appear at the same depth while ensuring they do not share the same parent. The solution runs in O(n) time and O(n) space.
Is Cousins in Binary Tree asked at Google/Amazon/Meta?
Binary tree relationship problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests understanding of tree traversal, BFS vs DFS reasoning, and handling parent-child relationships.
What data structure is used in Cousins in Binary Tree?
The main data structure is a binary tree. The BFS solution uses a queue to process nodes level by level, while the DFS solution relies on recursion or an explicit stack to track traversal along with parent and depth information.
What is the time complexity of Cousins in Binary Tree?
The optimal solutions run in O(n) time where n is the number of nodes in the binary tree. Both BFS level order traversal and DFS with parent-depth tracking visit each node at most once. Space complexity is O(n) for BFS and O(h) for DFS where h is the tree height.