Cousins in Binary Tree — Solution in Python, Java & C++
Cousins in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Cousins in Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and Bloomberg interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree whose node values are all distinct, and the values x and y of two different nodes in it.
Two nodes are cousins if they are at the same depth but have different parents. The root is at depth 0 and each child is one deeper than its parent.
Return true if the nodes holding x and y are cousins, and false otherwise.
Example 1
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Explanation: 4 is two levels down, 3 only one: different depths.
Example 2
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Explanation: 4 and 5 are both at depth 2, with parents 2 and 3.
Example 3
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false
Explanation: 2 and 3 share the same depth but also the same parent — they are siblings, not cousins.
Constraints
2 <= number of nodes <= 1001 <= Node.val <= 100all node values are distinctx != yx and y are both values in the tree
Hints for Cousins in Binary Tree
Hint 1
Two facts decide the answer for each of
xandy: how deep the node is, and who its parent is.Hint 2
One traversal can record both facts for both values — pass the depth and the parent down as you go.
Hint 3
Cousins means equal depths and different parents; siblings fail the second test.
How to solve Cousins in Binary Tree
Being cousins depends only on each node's depth and parent, so one traversal that carries (depth, parent) down to every node finds everything needed.
Approach
- Traverse the tree from the root with depth 0 and no parent (use a value that cannot occur, such as 0).
- At each node pass
depth + 1and the node's own value as the parent to its children. - When the node's value is
xory, record its depth and parent. - Return
trueexactly when the two depths are equal and the two parents differ.
Why it works
Values are distinct, so each of x and y is recorded once, with the true depth and parent of that node. The definition of cousins is precisely the final comparison.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion or stack
Pitfalls
- Same depth alone is not enough — siblings share a parent and are not cousins.
- A breadth-first search works too: check, level by level, whether both values appear in the same level and are not children of the same node.
Reference solution
Python
from typing import Optional
def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool:
found = {}
stack = [(root, 0, 0)] # node, depth, parent value (0: no parent)
while stack:
node, depth, parent = stack.pop()
if node.val == x or node.val == y:
found[node.val] = (depth, parent)
for child in (node.left, node.right):
if child:
stack.append((child, depth + 1, node.val))
dx, px = found[x]
dy, py = found[y]
return dx == dy and px != pyJava
public static boolean isCousins(TreeNode root, int x, int y) {
int[] info = new int[4]; // depth of x, parent of x, depth of y, parent of y
locate(root, 0, 0, x, y, info);
return info[0] == info[2] && info[1] != info[3];
}
static void locate(TreeNode node, int depth, int parent, int x, int y, int[] info) {
if (node == null) return;
if (node.val == x) { info[0] = depth; info[1] = parent; }
if (node.val == y) { info[2] = depth; info[3] = parent; }
locate(node.left, depth + 1, node.val, x, y, info);
locate(node.right, depth + 1, node.val, x, y, info);
}C++
void locate(TreeNode* node, int depth, int parent, int x, int y, int* info);
bool isCousins(TreeNode* root, int x, int y) {
int info[4] = {0, 0, 0, 0}; // depth of x, parent of x, depth of y, parent of y
locate(root, 0, 0, x, y, info);
return info[0] == info[2] && info[1] != info[3];
}
void locate(TreeNode* node, int depth, int parent, int x, int y, int* info) {
if (!node) return;
if (node->val == x) { info[0] = depth; info[1] = parent; }
if (node->val == y) { info[2] = depth; info[3] = parent; }
locate(node->left, depth + 1, node->val, x, y, info);
locate(node->right, depth + 1, node->val, x, y, info);
}JavaScript
var isCousins = function(root, x, y) {
var info = [0, 0, 0, 0]; // depth of x, parent of x, depth of y, parent of y
var stack = [[root, 0, 0]];
while (stack.length > 0) {
var top = stack.pop(), node = top[0], depth = top[1], parent = top[2];
if (node.val === x) { info[0] = depth; info[1] = parent; }
if (node.val === y) { info[2] = depth; info[3] = parent; }
if (node.left !== null) stack.push([node.left, depth + 1, node.val]);
if (node.right !== null) stack.push([node.right, depth + 1, node.val]);
}
return info[0] === info[2] && info[1] !== info[3];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)