Cousins in Binary Tree
Cousins in Binary Tree
Problem Description
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 considered cousins if they have the same depth but different parents.
Note that in a binary tree, the root node is at depth 0, and children of each depth k node are at depth k + 1.
Video Explanation
Approach
To determine if two nodes are cousins, we can use a Breadth-First Search (BFS) approach. We will traverse the tree level by level while keeping track of the parent of each node and their respective depths.
Steps:
-
Initialization: Use a queue to facilitate the BFS traversal. Store each node along with its parent and depth.
-
BFS Traversal:
- Dequeue each node from the front of the queue.
- If the current node has children, enqueue them along with their parent and the incremented depth.
- Check if both
xandyare found at the same depth but with different parents.
-
Return Result:
- If both nodes are found to be cousins during the traversal, return
true. - If the traversal ends without finding them, return
false.
- If both nodes are found to be cousins during the traversal, return
Solutions
- C++
- Java
- Python
- JavaScript
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
int xDepth = -1, yDepth = -1;
TreeNode *xParent = nullptr, *yParent = nullptr;
function<void(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode* node, TreeNode* parent, int depth) {
if (!node) return;
if (node->val == x) { xParent = parent; xDepth = depth; }
if (node->val == y) { yParent = parent; yDepth = depth; }
dfs(node->left, node, depth + 1);
dfs(node->right, node, depth + 1);
};
dfs(root, nullptr, 0);
return xDepth == yDepth && xParent != yParent;
}
};
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
if (root == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
boolean foundX = false, foundY = false;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// Check if both x and y are found at the same level
if (node.val == x) foundX = true;
if (node.val == y) foundY = true;
// Check for siblings (same parent)
if (node.left != null && node.right != null) {
if ((node.left.val == x && node.right.val == y) ||
(node.left.val == y && node.right.val == x)) {
return false; // x and y are siblings, not cousins
}
}
// Add child nodes to the queue
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
// If both x and y are found at the same level, they are cousins
if (foundX && foundY) return true;
}
return false; // Not cousins if the loop completes
}
}
//C++ Implementation
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
if (!root) return false;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
bool foundX = false, foundY = false;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
// Check if both x and y are found at the same level
if (node->val == x) foundX = true;
if (node->val == y) foundY = true;
// Check for siblings (same parent)
if (node->left && node->right) {
if ((node->left->val == x && node->right->val == y) ||
(node->left->val == y && node->right->val == x)) {
return false; // x and y are siblings, not cousins
}
}
// Add child nodes to the queue
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
// If both x and y are found at the same level, they are cousins
if (foundX && foundY) return true;
}
return false; // Not cousins if the loop completes
}
};
//Python Implementation
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
if not root:
return False
queue = deque([root])
while queue:
size = len(queue)
foundX = foundY = False
for _ in range(size):
node = queue.popleft()
# Check if both x and y are found at the same level
if node.val == x:
foundX = True
if node.val == y:
foundY = True
# Check for siblings (same parent)
if node.left and node.right:
if (node.left.val == x and node.right.val == y) or \
(node.left.val == y and node.right.val == x):
return False # x and y are siblings, not cousins
# Add child nodes to the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# If both x and y are found at the same level, they are cousins
if foundX and foundY:
return True
return False # Not cousins if the loop completes
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
res = []
def dfs(node, parent, depth):
if not node:
return
if node.val == x or node.val == y:
res.append((parent, depth))
dfs(node.left, node, depth + 1)
dfs(node.right, node, depth + 1)
dfs(root, None, 0)
return len(res) == 2 and res[0][1] == res[1][1] and res[0][0] != res[1][0]
var isCousins = function(root, x, y) {
let xDepth = -1, yDepth = -1;
let xParent = null, yParent = null;
function dfs(node, parent, depth) {
if (!node) return;
if (node.val === x) { xParent = parent; xDepth = depth; }
if (node.val === y) { yParent = parent; yDepth = depth; }
dfs(node.left, node, depth + 1);
dfs(node.right, node, depth + 1);
}
dfs(root, null, 0);
return xDepth === yDepth && xParent !== yParent;
};
Done with this topic? Mark it as complete to track your progress.
Related Practice Problems
Handpicked problems sharing similar algorithmic topic tags
Diameter of Binary Tree
Solving the Diameter of Binary Tree problem using a Recursive Depth-First Search (DFS) approach.
Maximum Depth of Binary Tree
Solving the Maximum Depth of Binary Tree problem using a Recursive Depth-First Search (DFS) approach.
Symmetric Tree
This document includes the solution to the problem of checking whether a binary tree is symmetric around its center, along with the approach and implementation.
💬 Discuss this page
Have a question or spot something confusing in "Cousins in Binary Tree"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.