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 != yxandyare 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;
}
}
}
Input
Output
#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
}
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output