Similar Problems
Similar Problems not available
Cousins In Binary Tree  Leetcode Solution
Companies:
LeetCode: Cousins In Binary Tree Leetcode Solution
Difficulty: Easy
Topics: binarytree tree depthfirstsearch breadthfirstsearch
Problem Statement:
Given a binary tree and two nodes of the tree p and q, the task is to find whether they are cousins or not.
Two nodes are said to be cousins of each other if they are at the same level of the binary tree and have different parents.
Solution:
To solve this problem, we will use a traversal algorithm (depthfirst search, DFS). During the traversal, we will keep track of the following information for each node: its parent node, its level in the binary tree.

Traverse the binary tree using depthfirst search.

For each node, record its level in the binary tree and its parent node.

If the levels of the given nodes (p and q) are the same and their parent nodes are different, then they are cousins.

If the levels of p and q are not the same, then they cannot be cousins.
Algorithm:

Initialize level and parent for root node.

Recursively traverse the binary tree and for each node:
a. If the current node is a left child of the parent node, set the level and parent values for the left child node.
b. If the current node is a right child of the parent node, set the level and parent values for the right child node.

Check if p and q have the same level and different parent nodes. If yes, return true, else return false.
Code:
class BinaryTreeNode:
def __init__(self, left=None, right=None, val=None):
self.left = left
self.right = right
self.val = val
def isCousin(root: BinaryTreeNode, p: BinaryTreeNode, q: BinaryTreeNode) > bool:
# level of p and q nodes
pLevel = findLevel(root, p, 1)
qLevel = findLevel(root, q, 1)
# parent of p and q nodes
pParent = findParent(root, p)
qParent = findParent(root, q)
# check if p and q are cousins
return pLevel == qLevel and pParent != qParent
# find level of a node in binary tree
def findLevel(root: BinaryTreeNode, node: BinaryTreeNode, level: int) > int:
if root is None or node is None:
return 0
if root == node:
return level
# search the left subtree
leftLevel = findLevel(root.left, node, level+1)
if leftLevel != 0:
return leftLevel
# search the right subtree
rightLevel = findLevel(root.right, node, level+1)
return rightLevel
# find parent of a node in binary tree
def findParent(root: BinaryTreeNode, node: BinaryTreeNode) > int:
if root is None or node is None:
return None
if root.left == node or root.right == node:
return root
# search the left subtree
leftParent = findParent(root.left, node)
if leftParent is not None:
return leftParent
# search the right subtree
rightParent = findParent(root.right, node)
return rightParent
Cousins In Binary Tree Solution Code
1