The "Cousins in Binary Tree" problem asks you to determine if two nodes in a binary tree are cousins. In this context, two nodes of a binary tree are considered cousins if:
You are given the root of a binary tree, and two integers x and y representing the values of two different nodes in the tree. Your task is to return true if the nodes with values x and y are cousins, or false otherwise.
Constraints:
To solve this problem, first, think about what it means for two nodes to be cousins:
The simplest approach would be to traverse the tree and, for each node, check if its children match x or y. But this would be inefficient, especially if we have to repeatedly traverse the tree to find both nodes.
A better way is to do a single traversal (either breadth-first or depth-first), keeping track of the depth and parent of each node as we go. Once we've found both x and y, we can compare their depths and parents to determine if they're cousins.
This thought process leads us from a brute-force approach (checking all pairs) to an optimized traversal that collects all the information we need in one pass.
We'll use either Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the tree while recording the depth and parent of each target node (x and y).
x or y:
x and y are found:
false.true; otherwise, return false.false.
Why this works: By storing the depth and parent for each target node, we can efficiently determine if the two nodes are cousins with just a single traversal of the tree.
Consider the following binary tree:
1
/ \
2 3
/ \
4 5
Suppose x = 4 and y = 5. Let's walk through the process:
null.x and y are at depth 2, but have different parents (2 and 3). So, they are cousins.
The output is true.
Brute-force Approach:
This is efficient and optimal for this problem.
The "Cousins in Binary Tree" problem is elegantly solved by traversing the tree once and recording the depth and parent for each target node. By comparing these values, we can quickly determine if the nodes are cousins. The key insight is to gather all necessary information in a single pass, making the solution both simple and efficient.
# Definition for a binary tree node.
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:
from collections import deque
queue = deque([(root, None, 0)]) # node, parent, depth
x_parent = y_parent = None
x_depth = y_depth = -1
while queue:
node, parent, depth = queue.popleft()
if node is None:
continue
if node.val == x:
x_parent, x_depth = parent, depth
if node.val == y:
y_parent, y_depth = parent, depth
if node.left:
queue.append((node.left, node, depth + 1))
if node.right:
queue.append((node.right, node, depth + 1))
return x_depth == y_depth and x_parent != y_parent
// Definition for a binary tree node.
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) {
std::queue<std::tuple<TreeNode*, TreeNode*, int>> q; // node, parent, depth
q.push({root, nullptr, 0});
TreeNode* x_parent = nullptr;
TreeNode* y_parent = nullptr;
int x_depth = -1, y_depth = -1;
while (!q.empty()) {
auto [node, parent, depth] = q.front(); q.pop();
if (!node) continue;
if (node->val == x) {
x_parent = parent;
x_depth = depth;
}
if (node->val == y) {
y_parent = parent;
y_depth = depth;
}
if (node->left) q.push({node->left, node, depth + 1});
if (node->right) q.push({node->right, node, depth + 1});
}
return x_depth == y_depth && x_parent != y_parent;
}
};
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
Queue<NodeInfo> queue = new LinkedList<>();
queue.offer(new NodeInfo(root, null, 0));
TreeNode xParent = null, yParent = null;
int xDepth = -1, yDepth = -1;
while (!queue.isEmpty()) {
NodeInfo info = queue.poll();
TreeNode node = info.node, parent = info.parent;
int depth = info.depth;
if (node == null) continue;
if (node.val == x) {
xParent = parent;
xDepth = depth;
}
if (node.val == y) {
yParent = parent;
yDepth = depth;
}
if (node.left != null) queue.offer(new NodeInfo(node.left, node, depth + 1));
if (node.right != null) queue.offer(new NodeInfo(node.right, node, depth + 1));
}
return xDepth == yDepth && xParent != yParent;
}
private static class NodeInfo {
TreeNode node, parent;
int depth;
NodeInfo(TreeNode node, TreeNode parent, int depth) {
this.node = node;
this.parent = parent;
this.depth = depth;
}
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} x
* @param {number} y
* @return {boolean}
*/
var isCousins = function(root, x, y) {
const queue = [[root, null, 0]]; // node, parent, depth
let xParent = null, yParent = null, xDepth = -1, yDepth = -1;
while (queue.length) {
const [node, parent, depth] = queue.shift();
if (!node) continue;
if (node.val === x) {
xParent = parent;
xDepth = depth;
}
if (node.val === y) {
yParent = parent;
yDepth = depth;
}
if (node.left) queue.push([node.left, node, depth + 1]);
if (node.right) queue.push([node.right, node, depth + 1]);
}
return xDepth === yDepth && xParent !== yParent;
};