## Algorithm

Problem Name: 993. Cousins in Binary Tree

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 != y
• x and y are exist in the tree.

## Code Examples

### #1 Code Example with Java Programming

Code - Java Programming

class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
ParentDepthPair xPair = getParentDepthPair(root, x, 0);
ParentDepthPair yPair = getParentDepthPair(root, y, 0);
return xPair.parent != yPair.parent && xPair.depth == yPair.depth;
}

private ParentDepthPair getParentDepthPair(TreeNode root, int val, int currDepth) {
if (root == null) {
return null;
}
if (root.val == val) {
return new ParentDepthPair(root, currDepth);
}
if ((root.left != null && root.left.val == val) || (root.right != null && root.right.val == val)) {
return new ParentDepthPair(root, currDepth);
}
ParentDepthPair leftPair = getParentDepthPair(root.left, val, currDepth + 1);
return leftPair != null ? leftPair : getParentDepthPair(root.right, val, currDepth + 1);
}

private static class ParentDepthPair {
TreeNode parent;
int depth;

public ParentDepthPair(TreeNode parent, int depth) {
this.parent = parent;
this.depth = depth;
}
}
}
Copy The Code &

Input

cmd
root = [1,2,3,4], x = 4, y = 3

Output

cmd
false

### #2 Code Example with Javascript Programming

Code - Javascript Programming

start coding...
const isCousins = (root, x, y, depth = 1, P = {}, D = {}) => {
let q = [root]
while (q.length) {
let K = q.length
while (K--) {
let p = q.shift()
if (p.left) {
if (p.left.val === x) (P.x = p.val), (D.x = depth)
if (p.left.val === y) (P.y = p.val), (D.y = depth)
q.push(p.left)
}
if (p.right) {
if (p.right.val === x) (P.x = p.val), (D.x = depth)
if (p.right.val === y) (P.y = p.val), (D.y = depth)
q.push(p.right)
}
}
++depth
}
return P.x !== P.y && D.x === D.y
}
Copy The Code &

Input

cmd
root = [1,2,3,4], x = 4, y = 3

Output

cmd
false

### #3 Code Example with Python Programming

Code - Python Programming

start coding...
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
def dfs(node, parent, depth, mod):
if node:
if node.val == mod:
return depth, parent
return dfs(node.left, node, depth + 1, mod) or dfs(node.right, node, depth + 1, mod)
dx, px, dy, py = dfs(root, None, 0, x) + dfs(root, None, 0, y)
return dx == dy and px != py
Copy The Code &

Input

cmd
root = [1,2,3,null,4,null,5], x = 5, y = 4

Output

cmd
true

### #4 Code Example with C# Programming

Code - C# Programming

start coding...
using System.Collections.Generic;

namespace LeetCode
{
public class _0993_CousinsInBinaryTree
{
public bool IsCousins(TreeNode root, int x, int y)
{
var queue = new Queue < TreeNode>();
queue.Enqueue(root);

while (queue.Count > 0)
{
var size = queue.Count;
bool siblings = false, cousins = false;

for (int i = 0; i  <  size; i++)
{
var node = queue.Dequeue();
if (node == null)
siblings = false;
else
{
if (node.val == x || node.val == y)
if (!cousins)
siblings = cousins = true;
else
return !siblings;

if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
queue.Enqueue(null);
}

if (cousins) return false;
}

return false;
}
}
}
Copy The Code &

Input

cmd
root = [1,2,3,null,4,null,5], x = 5, y = 4

Output

cmd
true